Местное население враждебно приняло новую власть. На «священную войну» против «неверных» поднялись все кавказские племена. Оружием их снабжали Турция и Англия, не желавшие укрепления России на Кавказе. Горцы собирались в отряды, нападали на форты, захватывали пленных. Царское правительство принимало активные меры, направленные на защиту южных владений. На побережье возводилась система военных укреплений, между которыми прокладывались дороги.
В середине 1830-х годов командующий войсками Кавказской линии и Черномории генерал-майор Вельяминов заложил первый русский стан на входе в Цемесскую бухту. Форт получил название Александровский. Строили его в невероятно тяжелых условиях, под охраной линейных стрелков. Жизнь первопроходцев была тяжелой. Частые нападения горцев, лихорадка, тиф опустошали гарнизоны. Но в столицах Кавказская война была овеяна ореолом романтики. Побывать на Кавказе стало модным. Сюда ссылали вольнодумцев и дуэлянтов, проигравшихся картежников и декабристов. В экспедициях Вельяминова служили ссыльные поэты Катенин и Лермонтов, декабристы Бестужев-Марлинский, Одоевский, Лорер, Кривцов и Лачинов.
В 1837 году начальником и ответственным за строительство береговых укреплений был назначен генерал Николай Раевский. В поисках новой крупной базы Черноморского флота он изучил всю подчиненную ему территорию, и выступил с предложением строить укрепление в вершине Суджукской бухты.
В сентябре 1838 года одиннадцать российских кораблей под командованием великого русского флотоводца вице-адмирал Михаила Лазарева вошли в Цемесскую бухту. В штабе, размещавшемся на линейном корабле "Силистрия", находились генерал-лейтенант Раевский, и будущий начальник первого отделения Черноморской береговой линии контр-адмирал Серебряков, который бывал здесь во время штурма Суджук – Кале. Хорошо зная местные обычаи и языки, Серебряков был советником правительства России в кавказском вопросе. К вечеру 12 сентября около шести тысяч человек с орудиями, боевым и обозным хозяйством высадились на берег Цемесской бухты. Окрестные племена, не оказывая сопротивления, ушли с насиженных мест.
Следуя добрым петровским традициям, освоение нового места началось со строительства адмиралтейства. Непривычный климат, сильные ветра, вызывали тяжелые болезни среди солдат и офицеров. Люди голодали. Подводы с провиантом надолго задерживались, а то и вовсе пропадали в пути. Сложно складывались отношения с местным населением. Но, несмотря на все невзгоды, на пологих склонах гор неустанно рос русский форштадт. Постепенно форт становится местом цивилизованной торговли. Дружески настроенные горцы находят здесь медицинскую помощь и защиту. Сам генерал разводит в укреплении фруктовые сады, привлекает к этому офицеров и солдат. В январе 1839 г. военный министр России издает приказ о присвоении укреплению названия Новороссийск.
Продолжателем дела Николая Раевского стал контр-адмирал Серебряков. В Новороссийск он прибыл в апреле 1839 года, и сразу же начал сооружение порта. Установив контакты со старейшинами окружающих племен, Серебряков доказывает им выгоду мирного сближения и полезность меновой торговли. Местные жители принимают участие в строительстве домов, торговых лавок, разведении садов и огородов. За 10 лет Новороссийск из военного лагеря превращается в город. На берегу русские купцы, армяне и греки держат торговые лавки. Горцы приезжают в город семьями, чтобы обменять овощи, фрукты и молоко на соль и ткани. Серебряков на деле доказывает местному населению готовность к просвещению, и учреждает школу для обучения детей горцев. В школе преподают Закон божий по Учению Магомета, чтение и письмо на турецком языке.
Но мирная жизнь Новороссийска длится недолго. Через 17 лет на долю города выпадают тяжкие испытания. О героической обороне Новороссийска во время Крымской войны не написаны книги, не сняты фильмы, но и сегодня она стоит в ряду славных ратных подвигов русских солдат. Понимая, что слабые укрепления Черноморской береговой линии будут уничтожены мощной англо-французской эскадрой, командование Черноморского флота ликвидирует их.
В Новороссийск вывозят более 5 тысяч человек со всех гарнизонов береговой линии.