В 1797 г. было разрешено на новом кладбище построить церковь, но была ли она построена – неизвестно. В 1830 г. сюда была перенесена деревянная церковь, оказавшаяся ненужной после построения каменного Покровского собора. Престол в ней был освящен в честь Всех святых.

В 1868 г. близ церкви Меленковским купцом Волковым была построена богадельня для престарелых и сирот.

Своей утвари кладбищенская церковь не имела. На богослужения все приносили из собора. В советские годы церковь была уничтожена.

Муром на Оке – древнейший город не только Владимирской земли, но и всей России. До начала русского государства все нижнее течение Оки было заселено финским племенем, которое летописец называет «Мурома». Уже в те времена, на берегу Оки находился Муром. Потом Муром оказался во власти Рюрика. С утверждением центра в Киеве, Муром попал в сферу влияния Киевского князя.

Владимир Святой, раздавая сыновьям города, отдал Муром младшему Глебу. Так было положено начало Муромскому княжеству. При князе Глебе в Муроме начинает распространяться христианство. Однако соседний народ – мордва придерживался язычества, а вследствие сношений с Волжскими булгарами, в Муроме было сильно влияние ислама. Поэтому в течение почти целого столетия, христианство в Муроме не имело успеха.

Когда в 1015 г. погиб князь Глеб, Муром снова перешел в непосредственное ведение великого князя Киевского. В княжение Ярослава I отдаленные от Киева города Муром и Ростов стал ссылочными местами для опальных бояр (так, в 1019 г. в Ростов был заточен Новгородский посадник Константин, а через два года, по приказу Ярослава, он был убит в Муроме). После смерти Ярослава в 1054 г. его сын Святослав получил в удел Чернигов и всю долину Оки вместе с Муромской землей. По смерти Святослава Ярославича Муромом завладел Олег.

В 1095 г. произошли несогласия между Олегом Святославичем и великим князем Святополком. Почти в то же время в Муром пришел из Курска сын Владимира Мономаха Изяслав. Муромцы охотно его приняли и выдали ему Олеговых посадников. В 1096 г. под Муромом произошла битва Олега и Изяслава, в которой Изяслав погиб. Тело его было погребено в муромском монастыре Св. Спаса. После этого Олег взял Ростов и Суздаль, но брат Изяслава Мстислав, отвоевал обратно эти города и преследовал Олега, который поручив Муром младшему брату Ярославу, бежал в Рязань.

В 1097 г. на Любечском съезде князей Муромско-Рязанское княжество было закреплено за Ярославом Святославичем, с которым связано принятие Муромом христианства. Поскольку летописи не упоминают ни об одном муромском князе Константине, историки отождествляют его с Ярославом Святославичем (Константином он мог быть назван в крещении или в монашестве).

Церковное предание, записанное в XVI в. в виде жития св. блгв. муромского князя Константина, говорит от этом событии так.

Князь Константин, услышав что в Муроме множество язычников, стал упрашивать отца своего Святослава, дать ему в удел этот город, дабы проповедовать там христианство. Долго отец не решался отпустить сына в языческий край, но наконец, благословив его иконой Богоматери, отпустил, дав для покорения города воевод и войско, а для просвещения епископа и священников. Это был 1092 г., семьдесят семь лет спустя мученической кончины св. кн. Глеба.

Не желая кровопролития, Константин послал вперед своего сына Михаила с малой дружиной для увещевания неверных к покорности. Муромцы пригласили Михаила в город для мирных переговоров, но убили его, а тело выбросили за город. На том месте, где лежало его тело, впоследствии была построена часовня. Она находилась при въезде с поля в московскую заставу, перед мостом через Успенский овраг. Убив княжеского сына, Муромцы затворились в своем городе, обнесенном каменными стенами. Но Константин, подступив к городу, взял его без кровопролития.