Год основания неизвестен, но наряду с Радомлем и Рясной Мстиславль — древнейшее поселение в земле радимичей. Впервые упоминался в уставной грамоте Смоленской епархии под 1150 г., в которой перечисляется среди смоленских населенных пунктов; город платил второе по величине после Торопца погородие [подать] епископу: 6 гривен урока, гривна почестья и 3 лисицы. По свидетельству сборника XVI в. киевского Златоверхого Михайловского монастыря, строителем Мстиславля был смоленский князь Ростислав Мстиславичпер. пол. XIII: «Лета 6642 [ 1135 г.] Ростислав Мстиславич устрой град великим Смоленескъ и церковь с[в]ятого Сп[а]са Верху Смыдыни и град Мстиславъль на Верхе онъ же созда».

Неправильно-округлый в плане детинец (площадь 1, 45 га) города занимает возвышенность между глубокими оврагами на правом берегу Вехры. По периметру детинец был укреплен валом, а с севера омывался ручьем Здоровец. Въезд в крепость был с юга.

Согласно Ипатьевской летописи, в 1156 г. под стенами Мстиславля стояло войско великого князя киевского Изяслава Давыдовича115759. Подавив с помощью половцев бесчинствовавшего на р. Десна племянника, князя Святослава Всеволодичаок. 111794, Изяслав вторгся в пределы его союзника, смоленского князя Ростислава Мстиславича, и вызвал на помощь дядю, новгородского князя Святослава Ольговича?1164. Та же летопись, однако, не сообщает о военных действиях, констатируя лишь, что Изяслав «стояще у Мстиславля сътвориша мир с сыновцами своими». Воскресенская летопись под 1180 г. сообщает, что сын Ростислава Роман отдал Мстиславль в удел своему сыну Мстиславу Романовичу Старому?1223. После смерти отца Мстислав в 1196 г. перешел на княжение в Смоленск, но Мстиславль оставил за собой. В кон. XIII в. город оказался на русско-литовском порубежье. В 1358 г. великий князь литовский Ольгерд134577 присоединил Мстиславль к Литве, посадил там своего наместника, а в 1377 г. отдал его в удел своему сыну Семёну13861431, ставшему по женской линии родоначальником князей Мстиславских.

В 1386 г. под Мстиславлем произошло ожесточенное сражение, в котором Семён Ольгердович разгромил войско смоленского князя Святослава Ивановича и союзных ему крестоносцев, причем в этой битве Святослав был убит. Семен был женат на сестре великого князя московского Василия I Дмитриевича13891425 Марии. Ему наследовали сын Юрий и внук Иван, от которого осталась дочь Юлиания (Ульяна). На ней женился ижеславский (заславский) князь Михаил Иванович?ок. 1528, которому великий князь литовский Александр Ягеллон14601506 в 1499 г. позволил именоваться князем Мстиславским и владеть уделом.

В 1537 г. его вдова построила в Мстиславле на свои средства у Троицкой церкви Нагорный монастырь. У них было двое сыновей: Василий, умерший еще при жизни отца, и Федор, перешедший в 1526 г. на службу в Москву и также принявший фамилию Мстиславского. Михаил, с согласия короля Сигизмунда I Старого13871437, усыновил королевича Сигизмунда-Августа и перед смертью в 1527 г. отказал ему Мстиславль , который в 1528 г. поступил в число коронных волостей и управлялся старостами. Первым старостой туда был назначен князь И. Соломерецкий.

В 1569 г. было учреждено Мстиславское воеводство, и первым воеводой стал Ю. Остик. Находясь на границе Московского государства и Литвы, Мстиславль постоянно был объектом нападений с обеих сторон, особенно в период Ливонской войны 1558– 1583 гг.

Во время раскопок Л. В. Алексеева в 1950-х гг. в Мстиславле был обнаружен фундамент каменной церкви кон. XII – нач. XIII вв. Также обнаружены деревянные настилы двух улиц, одна из которых пересекала город с юга на север. При раскопках найдены многочисленные бытовые вещи, а также писало, обломки стеклянного бокала с арабской надписью, шахматные фигурки, свинцовая пломба, тигельки, каменная литейная формочка, костяные пластины с тонкой резьбой, детали арбалета, кресты-энколпионы и берестяная грамота.

По предположению П. А. Раппопорта, «Мстиславль был лишь укрепленным двором, замком одного из князей Владимиро-Суздальской династии, вероятнее всего того князя, которому во второй половине XII в. принадлежал и Юрьев-Польский». По-видимому, это была княжеская резиденция, аналогичная Боголюбову при Владимире или Кидекше при Суздале.