В следующем году в Новгород прибыл брат Всеволода Изяслав, прогнанный дядей Георгием Суздальским из Турова, и просил себе помощи. Новгородцы зашумели, вызываясь на поход против властолюбивого Георгия. Вече было бурное: одни хотели защищать Мстиславичей, достать им волость, другие — нет. Большинство оказалось на стороне Мстиславичей, и положено было идти в поход. Князь Всеволод с братом и новгородским посадником пошли в Суздальскую землю. Но дорогой несогласия веча повторились в полках; противники Мстиславичей пересилили и заставили войско вернуться назад в Новгород, однако вече вольного города не одобрило этого, выбрало нового посадника, и князь Всеволод вместе с новгородцами отравился в Ростовскую землю. В то время прибыл в Новгород митрополит Киевский Михаил. Он уговаривал новгородцев не проливать братской крови: «Не ходите, меня Бог послушает!», но безуспешно. Новгородцы задержали святителя и отправили войско против князя Георгия под предводительством Всеволода. Стоял конец декабря. Метели и жестокий мороз преследовали новгородское войско и очень обессилили его. 26 января 1135 года произошло кровопролитное сражение на Ждановой горе. Суздальцев побито было не менее, чем новгородцев, но победы не было, и продолжать войну не приходилось. Заключили мир и новгородцы повернули домой. Эта неудача имела неприятные последствия для святого Всеволода. Новгородцы от него отвернулись. Они начали склоняться на сторону враждебных Мономаховичам князей Ольговичей Черниговских, которые в то время вели успешную борьбу против великого князя Ярополка Мстиславича. Призвав псковичей и ладожан, новгородцы думали с ними о том, как бы изгнать святого Всеволода. 28 мая 1136 года посадили его на епископском дворе под стражу вместе с женой, детьми и тещей. День и ночь стерегли князя 30 вооруженных сторожей. И так держали его до 15 июля. Князя обвиняли в следующих преступлениях: не заботился о смердах, то есть крестьянах; хотел, оставив Новгород, сесть в Переяславле; в сражении на Ждановой горе не обнаружил храбрости — первый отступил; вмешивает Новгород в усобицы: сначала велел приступить к Ольговичам, теперь отступить. Говорили, будто князь больше развлекается играми и охотой, чем управляет людьми и судит их. Так обвиняли князя люди враждебной ему стороны, которые взяли верх в вольном городе. На место святого князя новгородцы призвали к себе Святослава Ольговича. Когда приехал Святослав, то Всеволод отправился к великому князю в Киев, и Ярополк дал изгнаннику Вышгород.
Но у князя Всеволода были в Новгороде и Пскове люди, которые к нему были привязаны и по-другому ценили его деятельность в управлении вольным городом. Они тайно прислали к нему в Вышгород сказать: «Иди, князь, опять тебя хотят».
И действительно, псковичи из уважения к высоким душевным качествам князя Всеволода с радостью приняли его. По дороге в Псков он имел случай убедиться, что даже те, кто мог считать его в числе своих врагов, исполнены к нему расположения. Полоцкий князь Василий Рогволодович принял едущего в Псков Всеволода с истинно братской любовью. Он с дарами вышел к нему навстречу, ради заповеди Божией забыл все зло, которое сделал отец Всеволода Мстислав всему роду его, целовал с ним крест и с честью проводил святого Всеволода.
Господь не судил князю Всеволоду долго управлять Псковом. По своему пониманию долга на новом месте благоверный князь обратил главное свое внимание на внутреннюю жизнь горожан. Справедливый суд и управа, призрение странных и нищих, попечение о больных — вот ежедневные занятия князя. Почитая каждый день последним в своей жизни, он строгим воздержанием и молитвой приготовлял себе путь к вечности. Как раньше в Новгороде, так и теперь в Пскове святой Всеволод явил себя усердным храмоздателем. Он построил каменный соборный храм во имя Пресвятой Троицы.
Прошло около года пребывания его в Пскове. Новгородцы были смущены появлением их изгнанника в Пскове, а вместе чувствовали боязнь и раскаяние.