Первое упоминание о церкви Рождества Христова в Устюжне относится к 1547 году. Это был деревянный храм, построенный на средства прихожан. К XVII веку упоминания об этом храме исчезают.
В 1647 году произошло явление иконы Казанской Божией Матери устюженскому юродивому Афанасию, известному как «Железный посох». В честь этого события на средства горожанина Михаила Семёнова Олончанина был построен деревянный храм Явления иконы Казанской Богоматери. Однако в 1660 году церковь сгорела после удара молнии, хотя имущество, включая явленную икону, удалось спасти.
В 1675 году митрополит новгородский Корнилий выдал благословенную грамоту на строительство двух кладбищенских церквей на том же месте: холодной во имя Преполовения Пятидесятницы с приделом во имя Казанской иконы Божией Матери и тёплой во имя царевича Дмитрия. Обе церкви были деревянными и не имели прихода.
Согласно преданию, в конце царствования Алексея Михайловича Григорий Строганов, находясь в Устюжне, тяжело заболел, но излечился после молитвы перед явленной иконой Казанской Богоматери. В знак благодарности он дал обет построить в честь иконы новый каменный храм. В 1694 году на его средства была возведена каменная церковь с приделом Великомученицы Екатерины с северной стороны. Старые деревянные церкви были проданы другим приходам Устюжны и установлены на их территории. Строганов также пожаловал причту церкви пахотные земли и покосы в окрестностях города.
В середине XVIII века на средства устюженского помещика Василия Фёдоровича Козлянинова в церкви проводилась роспись интерьеров под руководством ярославских мастеров Ивана и Афанасия Андреевых Шустовых. В 1764—1767 годах при церкви была построена шатровая колокольня под руководством мастера Петра Белавина. К середине XIX века вокруг храма сформировалось кладбище с оградой, а в 1850-х годах был пристроен южный придел во имя Священномученика Антипия. Также была пристроена паперть с кладовыми, и произведены изменения в оконных проёмах западного фасада. В 1899 году фрески в интерьерах храма были отреставрированы художниками В. П. Китаевым, А. И. Кобыличным и С. Ф. Чуприненко на средства городского головы Николая Ивановича Поздеева.
После 1917 года храм продолжал действовать до 1937 года, когда был закрыт. В течение шести лет в здании размещался склад, но в 1943 году богослужения были возобновлены, и с тех пор храм не закрывался. В 1960 году комплекс церкви был признан памятником архитектуры республиканского значения и поставлен под государственную охрану. В 1970-х годах был проведён капитальный ремонт, включая выпрямление колокольни. К 1990-м годам состояние церкви вновь вызывало опасения из-за отсыревшей кладки и повреждений фресок. В 1995 году ансамбль церкви был признан объектом культурного наследия федерального значения, и в середине 1990-х годов интерьерные росписи были отреставрированы под руководством Сергея Павловича Белова.
