Впервые он упоминается в «Повести временных лет» под 980 г. В том же источнике под 988 г. записано, что Всеволод получил в держание от отца Владимиро-Волынскую область. Летописец сообщает, что это событие произошло после смерти Вышеслава Владимировича, то есть после 1010 г. Однако в скандинавской саге об Олафе Трюггвасоне говорится, что Всеволод бежал из Руси в Скандинавию, где и погиб около 995 г. Д. С. Лихачев полагает, что Всеволод бежал из Руси вследствие разрыва с отцом. Скорее всего Всеволод получил от отца Владимиро-Волынскую область в начале 90-х годов X в.
