В Сочинском музее краеведения собрано большое количество археологических находок, обнаруженных в окрестных пещерах и свидетельствующих о том, что здесь обитали многочисленные первобытные племена.

Впоследствии в течение продолжительного периода времени Черноморское побережье Кавказа было местом столкновения военно-политических и торговых интересов многих стран и народов. До 1829 г. им владела Турция и только после длительных войн оно отошло к России по мирному Адрианопольскому договору.
В 1837 г. Сухуми, Гагра и Адлер были заняты русскими войсками, но Сочинский мыс еще оставался в руках многочисленного воинственного рода племени убыхов, называвших себя «сшатче». По имени этого рода получила свое название река Сочи, а впоследствии и город.

В районе Сочи в первой половине XIX века развернулась жестокая кровопролитная борьба между русскими войсками и горскими племенами, побуждаемыми Турцией и Англией к борьбе против русских.
В 1837 г. при занятии мыса Адлер погиб поэт-декабрист А. А. Бестужев-Марлинский, который после отбытия в Сибири срока каторжных работ был сослан царизмом рядовым на Кавказ. Несмотря на свои боевые заслуги, А. А. Бестужев-Марлинский так и погиб рядовым солдатом.
Подобная же судьба постигла и поэта-декабриста А. И. Одоевского, который после 12 лет каторжных работ в Сибири тоже был сослан на Кавказ. Он умер в Лазаревском укреплении от злокачественной малярии.

В 1838 г. после упорного боя русский десантный, отряд высадился на Сочинском мысу, и на том месте, где сейчас расположен Сочинский маяк, было основано военное укрепление, вначале названное Александрией, а затем переименованное в Навагинское.
Убыхи, отступившие в горы и леса, еще целый ряд лет при помощи турок и англичан продолжали войну против русских, блокируя гарнизоны укреплений и совершая нападения на отдельные отряды.
Навагинское укрепление просуществовало до Крымской войны 1853—1856 гг. В этот период, по приказу царского командования, укрепление, как изолированное и не представляющее военного значения, было разрушено и эвакуировано.