Господь не судил князю Всеволоду долго управлять Псковом. По своему пониманию долга на новом месте благоверный князь обратил главное свое внимание на внутреннюю жизнь горожан. Справедливый суд и управа, призрение странных и нищих, попечение о больных — вот ежедневные занятия князя. Почитая каждый день последним в своей жизни, он строгим воздержанием и молитвой приготовлял себе путь к вечности. Как раньше в Новгороде, так и теперь в Пскове святой Всеволод явил себя усердным храмоздателем. Он построил каменный соборный храм во имя Пресвятой Троицы.
Прошло около года пребывания его в Пскове. Новгородцы были смущены появлением их изгнанника в Пскове, а вместе чувствовали боязнь и раскаяние. Восторжествовали в них чувства недобрые, и князь их Святослав в союзе с курянами и половцами пошел на Псков, чтобы прогнать Всеволода. Псковичи засекли в непроходимых лесах своих все дороги. Видя эту решительность псковичей, новгородцы со своим князем не захотели вести трудной войны со своими братьями. Между тем скоро не стало того, кто служил невольной причиной вражды. 11 февраля 1137 года, в четверг сырной недели, князь Всеволод почувствовал приближение смерти, причастился Святых Таин, простился с народом и мирно отошел ко Господу. Весь город, духовенство и миряне, старцы и дети, а особенно сирые и немощные, горько оплакивали общего добродетеля. Когда весть о смерти его пришла в Новгород, то возбудило во всех искреннее раскаяние, что не умели беречь у себя добродетельного князя. Тогда они решили, по крайней мере, останки его хранить у себя. Было снаряжено посольство в Псков во главе с протопопом Полюдом и лучшими людьми, чтобы взять и привезти тело в Новгород. Псковичи не смели противиться, но посланные из Новгорода никак не могли тронуть с места раку с телом почившего князя. Было ясно, что почившему неугодно было оставить свое тело тем, кто изгнал его при жизни. Новгородцы плакали и просили перед гробом прощения в своей самонадеянности и были утешены тем, что могли взять с собою ноготь, отпавший с перста почившего князя.
Согласно завещанию, тело святого князя было погребено в храме святого Димитрия Солунского. Прошло немного времени по преставлении благоверного князя и от его честных мощей начали истекать знамения и чудеса для приходящих с верою слепых, хромых, сухоруких, расслабленных, бесноватых и разных больных. Все они по вере своей и по молитвам святого князя получили исцеление. Прошло 55 лет. Память о князе Гаврииле-Всеволоде сохранялась псковичами свято, ибо он положил основание самостоятельности Пскова, дотоле считавшегося только пригородом Новгорода. В 1193 году святой князь явился в сонном видении одному богобоязненному мужу и сказал: «Объяви всему священному собору, князю, посаднику и всему христолюбивому народу псковскому, чтобы перенесли мощи мои от святого Димитрия в храм Пресвятыя Троицы; ибо там хочу я возлечь».
Благочестивый муж осмелился спросить: «Кто ты, владыко мой, пришедший ко мне, смиренному, воспомянуть грехи мои? От светлости лица твоего трепещет душа моя; открой мне имя твое святое». «Имя мое князь Всеволод, во святом крещении Гавриил, — отвечал явившийся, — Господь Иисус Христос предал мне град мой Псков, чтобы хранить его и соблюдать от безбожных немцев, и в нем хочу пребывать до скончания века сего. Не медли исполнить волю мою».
Обрадовались псковитяне и поспешили целым городом, в предшествии духовенства в церковь великомученика; там подняли раку чудотворца и понесли ее, но когда подошли к вратам города, которые назывались Смердиевыми, стала неподвижно рака. После многих напрасных усилий, слез и молитв принуждены были отнести мощи на прежнее место. В следующую ночь святой Всеволод явился тому же благоговейному мужу и сказал ему: «Не хочу идти во врата Смердии, но скажи князю и всему собору и посадникам: пусть пробьют ворота от реки Псковы на северную сторону и тут пронесут мощи мои в храм Пресвятыя Троицы».
Немедленно пробили городскую стену и сделали новые ворота, чрез которые внесли чудотворные мощи святого князя и поставили их открыто в возобновленном им соборном храме. Это перенесение мощей совершилось 27 ноября 1192 г.
В 1284 году при раке благоверного князя Всеволода совершилось чудо над бывшим псковским посадником Елисеем. Старый посадник лежал расслабленный всем телом, так что не мог двинуть ни рукой, ни ногой. По вере в благодатную силу святого Всеволода он велел отнести себя к его мощам. Когда священник, совершив молебствие, окропил больного святою водою, расслабленный встал и без посторонней помощи возвратился домой.
Ночью на 30 июля 1363 года святой князь явился соборному пономарю и сказал: «Поспеши передать соборянам Пресвятой Троицы и посадникам, чтобы вынесли из соборной церкви иконы и сосуды, ибо Господу угодно явить чудо над мощами моими в следующую ночь».