Подобно Андрею смотря с завистию на цветущую художествами и торговлею Болгарию, Всеволод желал овладеть ею и звал других Князей к содействию. Война с неверными казалась тогда во всяком случае справедливою: Святослав прислал сына своего, Владимира, к Великому Князю, радуясь, что он замыслил дело столь благоприятное для чести Российского оружия. Князья Рязанские, Муромский и сын Давида Смоленского также участвовали в сем походе. Рать союзников плыла Волгою до Казанской Губернии, оставила ладии близ устья Цывили, под стражею Белозерских воинов, и шла далее сухим путем. Передовой отряд, увидев вдали конницу, готовился к битве; но мнимые неприятели оказались Половцами, которые также воевали Болгарию и хотели служить Всеволоду. Вместе с ними Россияне осадили так называемый Великий город в земле Серебряных Болгаров, как сказано в летописи. Юный племянник Всеволодов, Изяслав Глебович, брат Князя Переяславского, не хотел ждать общего приступа и между тем, как Бояре советовались в шатре у Великого Князя, один с своею дружиною ударил на Болгарскую пехоту, стоявшую в укреплении пред городом; пробился до ворот, но, уязвленный стрелою в сердце, пал на землю. Воины принесли его в стан едва живого. Сей случай спас город: ибо Великий Князь, видя страдание любимого, мужественного племянника, не мог ревностно заниматься осадою и в десятый день, заключив мир с жителями, отступил к ладиям, где Белозерцы до его прибытия одержали победу над соединенными жителями трех городов Болгарских, хотевших истребить суда Россиян. Там Изяслав скончался, и Всеволод с горестию возвратился в столицу, отправив конницу в Владимир чрез землю Мордвы (нынешнюю Симбирскую и Нижегородскую губернии).
В сие время Россия западная узнала новых врагов, опасных и жестоких. Народ Литовский, в течение ста пятидесяти лет подвластный ее Князьям, дикий, бедный, платил им дань шкурами, даже лыками и вениками. Непрестанные наши междоусобия, разделение земли Кривской и слабость каждого Удела в особенности дали способ Литовцам не только освободиться от зависимости, но и тревожить набегами области Российские. Трубя в длинные свои трубы, они садились на борзых лесных коней и, как лютые звери, стремились на добычу: жгли селения, пленяли жителей и, настигаемые отрядами воинскими, не хотели биться стеною: рассыпаясь во все стороны, пускали стрелы издали, метали дротики, исчезали и снова являлись. Так сии грабители, несмотря на зимний холод, ужасно опустошили Псковскую область. Новогородцы, не успев защитить ее, винили в том своего Князя, Ярослава Владимировича, и на его место – кажется, с согласия Всеволодова – призвали к себе из Смоленска Давидова сына, Мстислава.
В России южной Князья соединили силы, чтобы смирить Половцев: Святослав Киевский, Рюрик с двумя племянниками, Владимир Нереяславский (внук Долгорукого), Глеб Юрьевич Туровский (правнук Святополка-Михаила) с братом Ярославом Пинским, Всеволод и Мстислав, сыновья Ярослава Луцкого, Мстислав Всеволодкович Городненский
