Идейная близость образов Всеволода Мстиславича и Довмонта в псковской традиции XIV–XVI вв. подчёркивается и тем обстоятельством, что «Житие Всеволода Мстиславича» анахронично представляет князя вслед за Довмонтом «оборонителем и забралом граду Пскову от поганых немец». В 1581 г., во время осады Пскова войсками польского короля Стефана Батория (1533–1586 гг.), старец псковского Покровского монастыря Дорофей видел около угловой Покровской башни, на месте будущего штурма, Пресвятую Богородицу, Которую умоляли о спасении города равноапостольный князь Владимир (Василий) Святославич и псковские святые (в их числе и Всеволод Мстиславич). 8 сентября, в критический момент боя, когда враги овладели южной частью города, псковичи принесли крестным ходом к месту сражения мощи Всеволода Мстиславича, отслужили молебен и к концу дня штурм был отбит. В память об этом событии для Покровской церкви была написана икона «явление Пресвятой Богородицы старцу Дорофею» (Псково-Покровская). Указания на предстательство Всеволода Мстиславича сохранились и в новгородских источниках, но только по отношению к Пскову: в 1342 г. псковичи, не получив от Литвы помощи против ордена, «положиша упование на Бога, и на Святую Богородицю, и на Всеволожу молитву, и на Тимофеову», после чего помирились с Новгородом. Факты церковного почитания Всеволода Мстиславича в Новгороде не выявлены, хотя в Житие, написанное священником Василием, включён эпизод о том, что после кончины князя новгородская депутация во главе с протопопом Софийского собора Полюдом (по другим источникам неизвестен) пыталась вывезти тело для погребения в Новгород, но «не подвижеся рака с места своего», и единственное, чего смогли по молитвам к Всеволоду Мстиславичу добиться новгородцы, это «ногтя от честныя руки» святого «Новуграду на утвержение и на исцеление недугом». Этот псковский рассказ, несомненно, позднего происхождения, но он отражает сложившееся (по крайней мере, уже в XIII в.) в Пскове представление о Всеволоде Мстиславиче как небесном покровителе и защитнике независимости от Новгорода. Своеобразная «парность» почитания святых Всеволода Мстиславича и Довмонта в Пскове подчёркивается и характерной деталью – появлением над захоронением Всеволода Мстиславича меча, что явно копирует положение меча над погребением скончавшегося в 1299 г. князя Довмонта в Троицком соборе. Клинок меча Всеволода Мстиславича с латинской надписью «Honorem meum nemini dabo» («Чести своей никому не отдам») изготовлен в Западной Европе в XV в., смонтирован с рукоятью в XVI в. Царь Иоанн IV Васильевич Грозный (1530–1584 гг.), молившийся у раки Всеволода Мстиславича в 1569 г., «удивися мечя его величествию». В правление великого князя Василия III Иоанновича (1479–1533 гг.), при псковском наместнике князе Иване Даниловиче Пенкове Ярославском, по заказу одного из исцелённых по молитвам к Всеволоду Мстиславичу на раку святого был изготовлен шитый покров, венец и цата на образе благоверного князя были сделаны из крупного жемчуга. В 1703 г. для мощей Всеволода Мстиславича был устроен придел его имени в новом Троицком соборе (конец XVII в.), а рака снабжена надписью: «1703 г., месяца априлия в 8 день освятися храм во имя святаго благовернаго и великаго князя Гавриила, в той же день и мощи его святые положены в нём при митрополите Иосифе Псковском и Изборском». При Петре I Алексеевиче (1672–1725 гг.) мощи были переложены под спуд. 22 апреля 1834 г., в день Святой Пасхи, по указу императора Николая I Павловича (1796–1855 гг.) дубовую колоду с мощами положили в новую серебряную раку и перенесли из придела в Троицкий собор. Гроб имел вид «длинного деревянного ящика с крышкою на больших петлях, обит железными обручами, обвит проволокою, на замке, с печатью». На раке было изображено несение мощей Всеволода Мстиславича на место битвы в 1581 г. и явление Пресвятой Богородицы старцу Дорофею. Мощи снова положили под спуд, но на раке стоял серебряный ковчег 1583 г. с частицами мощей (похищен в 1860 г.). На столпе около раки находилась древняя икона князя, прославившаяся чудотворениями в XVI в.; рядом с иконой висел меч Всеволода Мстиславича. В XIX в. в Пскове ежегодно в праздник Преполовения совершался крестный ход из Троицкого собора с образом Всеволода Мстиславича и Чирской иконой Божьей Матери на р. Великую, где освящалась вода. Во главе осеннего крестного хода, учреждённого в 1813 г. в память избавления Псковской и Санкт-Петербургской губерний от нашествия французских войск, торжественно несли мечи Всеволода Мстиславича и Довмонта, икону Всеволода Мстиславича и ковчег с частицей мощей святого. 27 ноября в Пскове ежегодно совершался крестный ход вокруг города в память о Всеволоде Мстиславиче. После революции 1917 г. мощи князя были вскрыты, драгоценная рака конфискована. В настоящее время мощи почивают в одной из уцелевших рак XIX в. на прежнем месте в псковском Троицком соборе. Наиболее древними агиографическими памятниками, относящимися к Всеволоду Мстиславичу, исследователи считают проложные редакции «Жития» и «Слова об обретении мощей», составление которых было связано, как полагают исследователи, с переложением мощей Всеволода Мстиславича в 1368 г.