В киевской летописи конца XII в. Мстиславу Ростиславичу посвящён обширный панегирический некролог. В нём говорится, в частности, что князь «всегда бо тосняшеться оумрети за Роускоую землю и за хрестьяны», что «не бе бо тое земле в Руси, которая же его не хотяшеть, ни любяшеть» и «плакашеся по немь вся земля Роуская, не може забыти доблести его» («Полное собрание русских летописей», том 2). В позднейшей традиции Мстислав Ростиславич известен под прозвищем Храбрый; впервые оно фиксируется в перечне новгородских князей в «Новгородской Первой Летописи» младшего извода (середина XV в.). До XX в. память Мстислава Ростиславича чтилась, в основном, местно. В «Книге, глаголемой Описание о российских святых», известной в списках XVIII–XIX вв., упоминается, что «святый и благоверный князь Мстислав Ростиславич преставися в лето 6637 (1129 г. – дату исследователи считают ошибочной)». Согласно описи 1617 г., в Софийском соборе «на правой стороне гроб аспидной, в нем мощи благовернаго князя Мстислава Ростиславича новгородскаго». Эта гробница Мстислава Ростиславича, изготовленная из сланцевого плитняка, в настоящее время находится на том же месте, в Рождественском приделе собора, между аркбутанами у южной стены. «Аспидная» гробница Мстислава Ростиславича упоминается и в памятнике «О святей соборной церкви Софии Премудрости Божии, иже в Велицем Новеграде, и о новгородских чудотворцех, идеже койждо лежит» (составленном при митрополите Киприане (Старорусенкове; 1626–1634 гг.)), в котором приводится местное предание, связанное с мощами князя: «...Рука у него, аки в защищение, поднята над персми, а гроба аспиднова угол отколот; а в повестех обноситца слышачи от древних, что де приходил Полоцкой князь изгоним на (В)еликии Новъгород и спрашивал, где лежит Мстислав Изяславич, и указаша ему, и он де извлек меч и хотел тять по мертвом телеси для того что бутто де мать его родила от него, Мстислава; и в те де поры Мстислав рукою своею поднял во гробе, и меч де ударился в аспидный гроб его, и тем де обычаем угол гроба отшибен; а писания о сем у Софии не сыскано». Захоронение Мстислава Ростиславича также отмечено в описи новгородских святынь 1634 г., составленной по распоряжению царицы Евдокии Лукьяновны, при этом сообщается, что мощи святого князя лежат «на верх земли», и приводится иное предание, отчасти явно легендарного характера: «...Глаголют... в повестех велми храбра на бранех и ходяща на Рим бранию. Мощи его нетленны, а рука ему правая выспрь». Наряду с Мстиславом Ростиславичем в «притворе» Софийского собора, согласно владычному летописанию, в 1178 г. был погребён его тёзка, князь Мстислав Ростиславич Безокий («Новгородская Первая Летопись»). Погребение «другого князя Мстислава» также отмечается в описаниях святых мощей Софийского собора (в северной части Рождественского придела), причём в описи, составленной около 1634 г., этот князь назван благоверным. Канонизация Мстислава Ростиславича подтверждена включением его имени в Собор Новгородских святых, празднование которому было возобновлено 10 июля 1981 г. (Собор учреждён около 1831 г.). Святому князю есть тропарь.