Строительство Козьмодемьянской церкви, находящейся в Муроме, относится к периоду 1556-1564 годов. Постройка была возведена в честь победы русских войск над Казанью. Точкой расположения памятника победе было выбрано место, где находилась старая деревянная церковь. Строительство церкви производилось на средства, пожертвованные самими прихожанами. Среди них были и наиболее богатые купцы города Мурома. Соответственно, построенная церковь была одной из наиболее красивых в этом городе.
Неизвестно точно имя архитектора храма. Однако есть предположение, что им стал Посник Яковлев, который строил храм Василия Блаженного в Москве (Покровская церковь на Красной площади возле Кремля).
Украшением Козьмодемьянской церкви служил высокий шатер, который своим внешним видом напоминал дозорную вышку или башню. Однако в 1868 этот шатер обрушился. До сих пор он не восстановлен. После того, как произошло обрушения шатра, церковная утварь и иконы были перенесены в Церковь Смоленской иконы Божией Матери, которая располагалась неподалеку. После этого она стала именоваться Новой Козьмодемьянской церковью.