It has not yet been determined how the village name Vedlozero (Vieljärvi in Karelian) came to be. A legend says that a merchant was travelling along a bumpy road and saw several lakes along the way. When he came to Vedlozero, he said in Karelian: «Vieyarvi, «meaning „another lake“ — and thus the name of the place was formed. Researchers think that the name could be derived from some proto-Sami word, but consider the connection between the place names Vedlozero /Vieljärvi/ and Vidlitsa /Videl/ indisputable. This is the name of the river that flows out from Lake Vedlozero and of the settlement located at the place where the river empties its waters into Lake Ladoga.

According to historical documents, the village was known in the 15 th century. Vedlozersky pogost belonged to Obonezhsky pyatina of the former Novgorod Feudal Republic, which was integrated into the Russian centralized state in 1478. Ancient books say that the village people were wealthy at the time. They grew rye, wheat, gathered hay, and fished, thus successfully feeding themselves.

At the beginning of the 20 th century, a separate Vedlozero volost existed, which was a part of the Olonets parish in the Olonets district. This volost united 6 communities (Vedlozerskoe, Nyalmozerskoe, Pannilskoe, Savinovskoe, and Shchekkilskoe) and 79 villages.