13 апреля 1838 г. в устье реки Сочи, в полукилометре от берега, выстроились боевые корабли. Эскадра под командованием контр-адмирала Артюхова начала бомбардировку убыхского аула (на его месте хотели заложить крепость). После обстрела аул взял штурмом высадившийся на берег десант. 21 апреля здесь заложили сначала временное укрепление. Назвали форт «Александрия» в честь императрицы Александры Федоровны (жены Николая I). Затем построили постоянную каменную крепость из привезенного керченского ракушечника и переименовали форт в «Навагинский» в честь полка, отличившегося в Кавказской войне (хотя боевых действиях в районе Сочи он не участвовал).