Гора Преображенская является знаменательным местом и своеобразным символом города Орска. Своё название гора получила «в честь праздника Преображения Господня, случившегося в день прибытия русских к устью реки Ори 6 августа 1735 года».

В начале XIX века Нагорная церковь была каменно-деревянной на цоколе из местного песчаника красно-коричневого цвета. Бревенчатые завершения (хорошо видные на рисунке Василия Жуковского 1837 года) придавали облику сооружения черты русской народной архитектуры.

К середине XIX века церковь на горе сильно обветшала, на каменных стенах появились значительные трещины. Уже в 1841 году она упоминается как «совершенно ветхая». Однако, церковь ещё долго простояла с незначительными ремонтами и только в 1873 году было принято решение о строительстве на горе нового каменного храма, однако работы долгое время не начинались.

27 июля 1888 года большой пожар окончательно уничтожил старую церковь и вновь встал вопрос о строительстве храма. Храм этот по многочисленным церковным документам числился «строящимся» вплоть до 1903 года.

Архитектором новой церкви стал академик Императорской Академии художеств Михаил Арефьевич Щурупов, известный своими проектами в Санкт-Петербурге (Крестовоздвиженский и Смоленский храм), Новгороде, Токио (Воскресенский собор), на Афоне в Греции (Андреевский скит).

Проект Никольской церкви стал одним из последних творений признанного архитектора с мировым именем — храм открылся через 2 года после смерти своего создателя.

Новый храм служил горожанам не только в роли религиозного объекта, но ещё и выступал в качестве своеобразного памятника посещения Орска наследником престола, цесаревичем Николаем Александровичем, в честь имени которого и был назван (посвящён Николаю Чудотворцу).

Революция вписала значимую страницу в историю культового сооружения, определив его дальнейшую судьбу. Летом 1918 года колокольня храма, как самая высокая точка на местности, служила красным в качестве наблюдательного пункта. Зная об этом, белые, чтобы сбить наблюдателя производили обстрел колокольни из орудий.

В 1930-е году все религиозные объекты в городе закрыли, а церковь заняла столовая Нефтесоюзстроя. 15 июня 1934 года издаётся записка заведующего горкомхозом об освобождении Нагорной церкви «на предмет разборки здания».

Оставшаяся после уничтожения колокольня долгое время использовалась для установки флажковой сигнализации пожарной команды, внутри же разместили резервуар для воды. В 1940-е годы колокольня числилась единственным памятником архитектуры из соображений сохранения геодезического пункта.

Несмотря на многочисленные предложения только в 1992 году начались практические действия по восстановлению храма. Именно тогда на вершине колокольни установили деревянный крест высотой 6,5 метров. Новый проект восстановления был разработан только в 1996 году, тогда же была начата его поэтапная реализация. 19 мая 1998 года полностью воссозданный в первозданном виде храм был освящён.