[[500-luku|500-luvulta]] aina [[1400-luku|1400-luvulle]] asti alue kuului vuorotellen [[Kasaarit|kasaareille]], [[Abhasia]]n kuningaskunnille ja viimeisimpänä Georgialle, minkä alaisuudessa nykyisen Sotšin kaupungin alueelle rakennettiin jopa tusinan verran kirkkoja. Muun muassa [[1000-luku|1000-luvulta]] peräisin olevan [[Bysantin valtakunta|bysanttilaisen]] [[Basilika (arkkitehtuuri)|basilikan]] rauniot ovat edelleen nähtävissä.
1400-luvusta lähtien rannikkoa hallitsivat [[Osmanien valtakunta|ottomaanit]] ja pieniltä osin paikalliset vuoristolaisklaanit.