На этом, как сообщает Н. М. Карамзин, внутренние междоусобицы прекратились, а начались войны внешние. Война с Болгарией, начатая Всеволодом Большое Гнездо в союзе почти со всеми князьями Земли Русской, в том числе и черниговскими, имела своей целью не просто усмирение своих волжских соседей, а завоевание и подчинение этого государства. Кроме торговых интересов Владимирского княжества, в этой войне были актуальными вопросы веры: болгары еще в X в. стали исповедовать ислам, так что справедливость такой войны была освящена опытом крестовых походов во всей Европе. Война не принесла полной победы над болгарами, но и достигнутого было достаточно для успешной торговли.
Еще одним противником владимирского князя, да и других тоже, стали литовцы, жившие в дремучих лесах, которых ранее русские князья принуждали платить дань. О происхождении и жизни литовцев до XIII в. ничего не известно. Первое упоминание этого этнонима зафиксировано только в «Кведлибургских анналах» при описании миссионерской деятельности архиепископа Бруно, который стал проповедовать среди «черных венгров» в Трансильвании, печенегов и пруссов, где «на пограничье Руси и Литвы» после крещения некоего вождя литовского племени Нетимера он погиб в 1009 г. от рук языческих фанатиков того же племени.
Сами литовцы еще с XV–XVI вв. выводят свое происхождение, как и многие другие народы, от римлян. Вот как версию этой легенды представил Михалон Литвин в 1550 г.:
«Ведь пришли в эти края наши предки, воины и граждане римские, посланные некогда в колонии (in colonias), чтобы отогнать прочь от своих границ скифские народы (gentes Scythicas). Или в соответствии с более правильной точкой зрения, они были занесены бурями Океана при Г. Юлии Цезаре. Действительно, когда этот Цезарь, как пишет Луций Флор (Luc Floras), победил и перебил германцев (Germanis) в Галлии, и, покорив ближайшую часть Германии, переправился через Рейн (Rhenum) и [поплыл] по океану в Британию (in Britanniam), и его флот был разметан бурей, [и] плавание было не слишком удачно, и пристали корабли предков наших к побережью, то, как полагают, они вышли на сушу там, где ныне находится крепость Жемайтии Плотели (Ploteli). Ибо и в наше время приставали иные заморские корабли к этому самому побережью. Здесь наши предки, утомленные и морскими трудностями и опасностями, и владеющие огромным количеством пленных, как мужчин, так и женщин, начали жить в шатрах с очагами, по военному обычаю, до сих [пор] бытующему в Жемайтии» [48, 86].
Михалон ссылается здесь на римского историка II в. Луция Флора, который изложил историю римских завоеваний, в основном построенную на извлечениях из истории Тита Ливия, описание завоевания Британии которого до нашего времени не дошло. Этим источником широко пользовались и другие польские историки – Длугош, Бельский, Стрыйковский. Вот только крепость Плотели (Plateliai) находилась и во времена Михалона далеко от моря, так что в легенде, скорее всего, подразумевалось побережье Паланги.