После Крымской войны все Черноморское побережье Кавказа и весь Закубанский край остались за Россией. Однако Кавказская война продолжалась. Проживающие на огромной территории многочисленные адыгейские племена, подстрекаемые англо-турецкой агентурой, вели упорную борьбу с царскими войсками. Горцы удерживали большинство русских укреплений Черноморской береговой линии, оставленных во время Крымской войны. Так на развалинах Новороссийского укрепления и крепости Анапа располагался черкесский князь Сефер-бей.

В условиях продолжавшейся Кавказской войны правительство Александра II решает в первую очередь занять и восстановить разрушенные укрепления на Черноморском побережье. Так на месте Новороссийского укрепления в 1858 году появляется Константиновское укрепление.

После того как в Крымскую войну в 1855 году Новороссийское укрепление было оставлено, на его месте в 1858 году было основано Константиновское укрепление.
1860 году был образован Натухайский округ с центром в Константиновском укреплении.

25 июля 1862 года был издан приказ №332 по Кавказской армии, в котором значилось, что в Натухайском округе были водворены 25 станиц. Таким образом около Константиновского укрепления появилась Новороссийская станица.

В станицу Новороссийскую еще в апреле и июне этого же года были переселены 1 офицерская и 99 казачьих семей из Кубанского и Азовского казачьего войска – это 275 мужского и 234 женского пола. [6] К концу года в станице было 62 построенных дома и 27 недостроенных. [1]

129 лет назад – 23 мая 1896 года – произошло ключевое событие – Новороссийск стал столицей Черноморской губернии!

Начав свою историю как военное укрепление в 1838 году, будучи оставлен в Крымскую войну в 1855 году, заново родившись в 1858 году, Новороссийск становится центром Черноморского округа в 1866 году и, наконец, достигает пика своей карьеры в 1896 году – становится столицей целой губернии.