Die Zeit zwischen dem 6. und dem 15. Jahrhundert gehörte den Königen der Georgier. Duzende von Kirchen, die in dieser Zeitspanne gebaut wurden, zeugen von der frühen Christianisierung der Gebietes. Georgien war eines der ersten Christlichen Länder überhaupt. Im Ortsteil Loo im Stadtbezirk Lasarewski steht zum Beispiel die sehenswerte Ruine einer byzantinischen Basilika aus dem 11. Jahrhundert.
Ab dem 15. Jahrhundert war Sochi dann eine Kolonie des Osmanischen Reiches. Erst nach dem Russisch-Türkischen Krieg 1828–1829 traten die Osmanen Sochi mit dem Frieden von Adrianopel an die russischen Zaren ab. Sochi gehörte nun zu Russland.
Im Jahr 1838 wurd an Stelle des heutigen Sochi eine Siedlung mit Bestestigungsanlagen gebaut, das Fort Alexandrija (Александрия). Weitere Befestigungsanlagen, die heute jeweils die Kerne der Rajons von Sochi bilden, entstanden kurze Zeit später, so das Fort des Heiligen Geistes (Fort Swjatowo Ducha, 1837, heute Adler), Lasarewski und Golowinski (1839, heute Lasarewskoje und Golowinka). Entsprechend dem Namen des dort fest stationierten russischen Regimentes wurde Alexandrija im Jahr 1839 in Nawaginskoje umbenannt.
