Храм во имя Николая Чудотворца в пригородном селе Терновка был построен в 1847 году, и в том же году состоялось освящение левого придела во имя мученицы Параскевы, нареченной Пятница. В 1850 году освящен главный престол во имя святителя Николая, архиепископа Мирликийского, а в 1864 году - правый придел в честь святителя Тихона Задонского.
В 1933 году храм закрыли, разместив в нем вначале склад, а затем кинотеатр «Сура». Завершение храма и колокольня были сломаны.
В 1995 году здание вернули верующим, и началось восстановление храма. В 1998 году восстановили купол, а также соорудили ограду, В 2004 году расписали алтарь священными изображениями, а в следующем году установили новый иконостас.