Знаменитый историк искусства Русского Севера В. П. Выголов для датировки храма Рождества Христова использовал два материала, обнаруженные случайно им в фондах Тотемского краеведческого музея. Речь идёт о рукописи местного историка, краеведа и искусствоведа Д. М. Григорова «Город Тотьма. Исторический очерк», созданной в 1910-1920-е годы, и о буклете «Памятка о достопримечательностях города Тотьмы и его окрестностей», вышедшем здесь же, в Тотьме, в 1916 году. Выголов на основе анализа смог установить, что храм строился в два приёма, с большим временным промежутком между этапами. Так, нижний этаж здания был сооружён в 1746-1748 годах, верхний в 1786-1793 годах. Одновременно с верхним этажом появилась и колокольня, к сожалению, не сохранившаяся до наших дней. Имена зодчих, строивших церковь, до сих пор остаются неизвестными. Интересно, что архитектору, трудившимся над верхней частью здания, удалось весьма органично совместить разновременные части, при всех заметных отличиях нижнего и верхнего ярусов, постройка тем не менее выглядит цельной. Также не известно и имя заказчика тотемского храма во имя Рождества Христова. Есть некоторая вероятность, что возведение этого храма как-то связано с тотемским купцом Алексеем Нератовым, но достоверность довольно сомнительна.
Шедевр тотемского барокко Рождественская церковь, не первый храм с таким посвящением в Тотьме. Есть сведения, что древнейшая Рождественская церковь, уже существовала в начале ХVII века, неподалёку стоял храм во имя Николая Чудотворца, а причт у обеих церквей был общим. В переписной книге 1646 года упомянута перестройка Никольской церкви, «В том же Ерзовском переулке церковь вновь ставят о два придела — Николая Чудотворца да великомученицы Параскевы, нарицаемой Пятницы». При этом писец не называет причину возведения нового здания. Кроме этого сообщается, что на церковной земле поставлены пять келий, в которых живут старицы и вдовы. Дальнейшая судьба этих храмов не известна. Есть основания предполагать, что они сгорели в сильнейшем тотемском пожаре 1743 года. Деревянные Рождественская и Никольская церкви возродились в едином каменном здании в том же ХVIII веке. Престол храма нижнего этажа был освящён в честь Рождества Христова, и по этому посвящению называют всю церковь целиком, а престол верхнего храма, устроенного позже, стал Никольским.
Церковь в честь Рождества Христова была закрыта в 1930-е годы. Стоявшую рядом с ней колокольню с храмом во имя святой Параскевы Пятницы в нижнем ярусе вовсе разрушили. Практически всё внутреннее убранство оказалось утрачено. Церковное здание использовалось в хозяйственных целях.
В 1990-х годах эпоха безвременья закончилась. В 1995 году Рождественская церковь была передана Вологодской епархии, началось восстановление храма. Его освящение иерейским чином состоялось в 1999 году. Пожалуй, самое значительное церковное событие в современной жизни Рождественской церкви связано с перенесением в неё мощей покровителя Тотьмы преподобного Феодосия Суморина. В 1988 году, в ознаименование празднования 1000-летия Крещения руси, Вологодский музей передал Вологодской епархии мощи святого. Первоначально их поместили в Лазаревский храм Вологды, а в 1994 году, по просьбе верующих тотьмичей, состоялось торжественное перенесение святых останков в Тотьму. До возобновления полноценной церковной жизни Рождественского храма они находились в Троицкой церкви Зеленской слободы. До сентября 2016 года мощи святого почивали в нижнем ярусе Рождественского храма, после чего 15 сентября 2016 года были перенесены с крестным ходом в основанную прп. Феодосием Спасо-Суморину обитель.
