В середине XIX века в Камышлове была построена кладбищенская церковь, освященная во имя святителя Николая Чудотворца. Этот деревянный храм служил местом проведения богослужений, включая отпевания усопших, и являлся важным духовным центром для местного населения.
В 1935 году, в период активной антирелигиозной политики советской власти, Свято-Николаевская церковь была закрыта по постановлению Камышловского районного исполнительного комитета. Здание храма было разрушено с использованием строительной техники, что привело к полной ликвидации сооружения.
В начале 1990-х годов, с изменением государственной политики в отношении религии, православный приход Камышлова инициировал строительство нового храма на месте ранее разрушенной церкви. Новый храм было решено освятить во имя Сорока Севастийских мучеников. Строительство началось при поддержке некоторых городских предприятий: был заложен фундамент и возведены первые ряды кирпичной кладки. Однако из-за нестабильной экономической ситуации в стране работы были приостановлены и заморожены на десять лет.
В 2004 году строительство храма было возобновлено. К настоящему времени здание храма завершено, проведены внутренние отделочные работы, территория вокруг благоустроена: обустроены детская площадка и цветники, возведена каменная ограда. С 2009 года при храме функционирует воскресная школа для детей.
