С 1097 года город становится столицей Муромо-Рязанского княжества, с середины XII века до начала XV века – столицей Муромского княжества. Самым известным историческим персонажем города стал русский богатырь, воспетый множеством былин, легенд и сказаний Илья Муромец, само имя которого определяет место его рождения. С детства Илья был очень слабым и не мог ходить. Однажды к нему явился Николай Чудотворец и попросил воды. Илья ответил, что не может подать водицы, потому что не может встать. Николай Чудотворец тут же повелел Илье – «Встань, и иди!». Свершилось чудо. Илья не только стал ходить, но и обрел богатырскую силу, которая помогла ему в дальнейшем совершить множество геройских подвигов. В соборном храме Спасо-Преображенской обители находится рака с частицей мощей преподобного Илии Муромца.
В 1097 году город был отдан младшему брату князя Олега Святославовича Ярославу. Ярослав глубоко интересовался вопросами веры и был в переписке с митрополитом Никифором. По церковному преданию он основал Переславль Рязанский и первые храмы – во имя Благовещения, Бориса и Глеба, а также первый монастырь во имя Спаса (1096) в Муроме. Князь Ярослав считается родоначальником муромских и рязанских князей. Умер он в 1129.
После смерти Ярослава Мудрого город находился под властью его сына Юрия Ярославича, а с 1143 по 1145 под властью его третьего сына, черниговского князя Святослава. Муром процветал, в нем бурно развивались ремесла и торговля, чему способствовала широкая Ока. В 1088 году на город напали волжско-камские булгары, которые разорили и сожгли его. Но Муром, активно воспользовавшийся своим выгодным географическим положением, быстро восстановился.
В конце XI века в Муром прибыл князь Константин, желавший упрочить в Муроме влияние христианства. Вместе с ним приехали его сыновья Михаил и Федор и супруга Ирина. Желая убедить жителей в своих мирных и добрых намерениях, он послал своего сына Михаила вперед. Михаил был убит. Тогда в город князю пришлось войти с дружиной. Возле могилы сына, Константин воздвиг храм во имя Благовещения Пресвятой Богородицы. Еще долго мурома сопротивлялись крещению, но благодаря чудесному знамению – светящейся иконе Богородицы, – Константин, все же, смог убедить их креститься. В водах Оки их крестил епископ Василий. Константин, Михаил и Федор канонизированы, их мощи, над которыми и по сей день совершаются чудеса, покоятся в основанном князем Благовещенском монастыре.