О судьбе племянников, сыновей давно скончавшегося старшего брата Ростислава Юрьевича, Михаилу почему-то не удалось договориться. Ярополк остался в плену, а его брат Мстислав лишился княжения в Треполье. Возможно, эти князья вызвали возмущение у смоленских Ростиславичей своим неподобающим поведением.
Освободившись от плена, Всеволод поехал к брату Михаилу в Переяславль-Южный. Там вскоре им пришлось взять под свою защиту сестру Ольгу, которая была вынуждена бежать с сыном Владимиром от мужа – князя Ярослава Галичского. Новый великий князь Киевский Рюрик Ростиславич стал требовать выдачи княгини с сыном галичскому князю, хотя знал, что в Галиче они могут оказаться в темнице.
Все знали, что Ярослав Галичский завел любовницу Настаску и хотел провозгласить своим наследником ее сына Олега. Законная супруга и старший сын Владимир мешали ему в осуществлении этих планов. Чтобы не оказаться в темнице, им пришлось спасаться бегством.
Об ущемлении интересов сестры и племянника Михаил Юрьевич и Всеволод были вынуждены написать Андрею Боголюбскому. Сообщенная ими информация еще больше настроила владимиро-суздальского князя против смоленских Ростиславичей. Он связался со своим союзником, черниговским князем Святославом Всеволодовичем, и стал готовиться к новому походу на Киев. В состав объединенного войска вошли и дружины Михаила и Всеволода Юрьевичей. Общее его число достигло 50 тысяч воинов.
В 1174 г. Андрей Боголюбский приказал сыну Юрию, стоящему во главе полков, изгнать Рюрика и Давыда Ростиславичей из Киевского княжества, а Мстислава Ростиславича, как самого дерзкого и непочтительного к нему князя, доставить во Владимир.
Первую часть его задания оказалось несложно выполнить. Рюрик с Давыдом заранее уехали из Киева, но Мстислав, находящийся в Вышгороде, решил стоять до конца.
На военном совете всех 20 князей, участвовавших в походе на Киев, постановили, что к Вышгороду отправятся полки Всеволода Юрьевича и Игоря Святославича, сына Святослава Всеволодовича Черниговского, как уже отмечалось, героя знаменитого «Слова о полку Игореве».
Совместные бои еще больше сдружили двух знаменитых древнерусских князей. Несомненно, что Всеволод рассказал Игорю о проблемах его тещи, княгини Ольги Юрьевны, и тот выразил желание ей помочь. Известно, что сын княгини Владимир даже переехал в Новгород-Северский и стал жить при дворе Игоря Святославича.
Правда, сражения Всеволода и Игоря с отчаянно сопротивлявшимся Мстиславом Ростиславичем оказались неудачными. Вряд ли в этом была вина еще достаточно молодых и не очень опытных военачальников. Ведь Мстислав Ростиславич, по отзывам современников, был одним из самых отважных и талантливейших русских полководцев того времени.
В летописях битва князей под Вышгородом описана достаточно подробно. Сначала Всеволод с Игорем разделили свои полки на три части. В центре расположился Всеволод со своими дружинниками, по бокам новгородцы и ростовцы, присланные Андреем Боголюбским, рядом с ними черниговцы Игоря.
Мстислав, узнав о расположении полков противников, ударил в центр, поскольку понимал, что у молодого Всеволода мало воинского опыта. Расчет оказался верным, вскоре ему удалось смять дружину Всеволода, но новгородцы, ростовцы и черниговцы попытались его окружить. Разгорелась ожесточенная битва с множеством убитых и раненых с двух сторон. Это вынудило Мстислава Ростиславича отступить в Вышгород.
Несколько дней Всеволод с Игорем пытались приступами взять город, но осадных орудий у них не было. Почти девять недель простояли они под стенами, пока не узнали, что из Луцка на помощь Мстиславу идет Ярослав Изяславич, пожелавший стать новым киевским князем и договорившийся об этом с Ростиславичами.
Золотой амулет Владимира Мономаха
Всеволоду с Игорем пришлось снять осаду Вышгорода и вернуться в свои города ни с чем. Вполне вероятно, что эта неудача расстроила горячих и честолюбивых князей. Но бороться с сильным кланом смоленских Ростиславичей в одиночку они не могли.
В Переяславле-Южном, которым правил брат Михаил Юрьевич, Всеволода ждали супруга Мария с двумя дочерьми. Семья его постепенно увеличивалась, хотя собственных земельных владений все еще не было. В условиях постоянных междоусобных баталий и неуступчивости старшего брата Андрея Боголюбского получить их было очень сложно.
В конце 1174 г. из Суздаля пришла печальная весть – там скончался брат Михаила и Всеволода Святослав. С детских лет страдал он от неизлечимой болезни, но никогда не роптал и мужественно переносил все страдания. Летописец написал о том, что Святослав был воистину Божий угодник, избранный из всех князей. Бог не дал ему княжить на земле, но дал ему царство небесное. Уважая брата-калеку, Андрей Боголюбский позволил ему жить в Суздале и потом с честью похоронил в главном суздальском соборе.