Деревянная церковь Святой Живоначальной Троицы на Редятине улице (в Ямской слободе) была построена в 1165 году. Строительство каменной церкви, согласно летописям, датируется 1365 годом. Строителями были югорцы — те горожане, которые были тесно связаны какой-либо деятельностью с Югрой (в то время Северный Урал).

В 1734 году здание было капитально перестроено: был сохранён план, сохранилось расположение входов, стены на высоту 1,5-2 м, частично использован материал XIV века, однако облик фасада и интерьера существенно меняется. Церковь отличается пониженной апсидой без портальной арки, крещатыми столбами, восьмигранным барабаном с лопатками на углах, угловыми сводами оригинальной конструкции, обилием голосников в стенах барабана и парусах, богатым изразцовым декором барабана. Церковь XIV века была четырёхстолпной, без притворов, с двумя пониженными апсидами помимо центральной, имела трёхлопастное завершение, была декорирована слабо, не имела лопаток на фасадах.

В 1830 году основной объём вновь перестроен, пристроены каменные паперть, трапезная и колокольня (до этого они были возведены в конце XVIII века в дереве). В 1975—1979 гг. под руководством Л. Е. Красноречьева храм исследован и реставрирован по состоянию на XVIII век, остатки храма XIV века в интерьере раскрыты и законсервированы в нижней части интерьера, оформленной в виде подцерковья.

Несмотря на то, что здание храма не столь большое и богатое по сравнению с другими обителями, церковь была включена в список всемирного наследия Юнеско. Это связано с тем, что сооружение является архитектурным памятником сразу 3 столетий.