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.