До революции в Новороссийске существовал Никольский собор, построенный в 1846 году. Во время Крымской войны и после временного упразднения города он был частично разрушен, но затем восстановлен и реконструирован после возвращения русских. В 1930 году собор закрыли и переоборудовали в гарнизонный клуб, а в 1931 году его разрушили. Сейчас на этом месте находится кафе «Театральное» в Парке культуры и отдыха имени Ленина.

В 1892 году в Новороссийске было два храма: Николаевский и Скорбященский. Николаевская церковь, старейшая в городе, была построена в 1846 году и располагалась в первой части города на площади, известной как Церковная (ныне Ленинский Парк). Она была каменной и покрыта железом. Скорбященская церковь находилась во второй части города, Зацемесской, которая до 1900 года не входила в городскую черту. Эта церковь была деревянной и ветхой. При этих церквях начали появляться первые церковно-приходские школы для мальчиков и девочек. Первое упоминание о таких школах относится к Николаевскому собору. Организацией приходских школ занимался настоятель, отец Михаил Павлов, который подавал прошения об их открытии и выделении земельных участков для строительства рядом с храмом.