В 1667 г. исетский казак Давыд Андреев подал Тобольскому воеводе челобитную, в которой просил разрешения построить в дельте речки Терсяка новый острог. Разрешение было получено. Так в 1668 г. возник Терсюкский (Терсяцкий) острог и одноимённая слобода, расположившаяся на левом берегу Исети, при протоке Быстрой (Исецкой). Эта глубокая и бурная в то время речка имела и другое название - Терсючок и, как и река Терсюк, несла в себе память о проживавшей здесь в XV-XVII в. в. этнической группе сибирских татар - «терсяков».
Считается, что одновременно с основанием острога и слободы в 1668 г., была возведена и церковь во имя Святой Великомученицы Екатерины. По другим сведениям храм этот был освящен в честь Святителя Николая. Храм был деревянным. В 1846-1855 г. г. в с. Терсюкском была выстроена новая каменная церковь.
Храм чаще всего именовался Николаевско-Екатерининским. Он был закрыт решением общего собрания граждан в 1930 г. (по другим сведениям – в 1929 г.) К 1947 г. церковь была переоборудована и занята под склад зерна. К 1961 г. к храму, уже утратившему внешний церковный вид, была произведена капитальная пристройка. К этому времени куполов на здании уже не было и оно использовалось под сельский клуб. Восстановление храма началось в 2005 г. Были установлены рамы и окрашены решетки в окнах, выборочно оштукатурены и выбелены стены.
Первый молебен состоялся 12 июля 2005 г., в день Первоверховных Апостолов Петра и Павла.