De okroeg werd in 1866 opgericht nadat Rusland in de eindfase van de Kaukasusoorlog het noord-Kaukasische Circassië veroverd had, waar het gebied tot dan toe behoorde. In 1868 werd het gebied langs de noordoostelijke kust van de Zwarte Zee tot en met de stad Anapa toegevoegd aan het okroeg. In 1870 werd de okroeg ingedeeld in drie secties (oetsjatsjok), te weten Toeapse, Novorossiejsk en Sotsji. In 1870 werd de status van deze secties verlaagd tot otdel.
In 1884 werd Anapa overgeheveld naar het oblast Koeban. Op 21 maart 1888 werd de onafhankelijke bestuurlijke status van het okroeg opgeheven en werd het opgenomen in het oblast Koeban. De okroeg werd op 23 mei 1896 getransformeerd in het Zwarte Zee-gouvernement met hoofdstad Novorossiejsk, waarmee het weer buiten het oblast Koeban werd geplaatst. Binnen dat gouvernement werden de eerdere secties tot okroeg gepromoveerd: Toeapse, Novorossiejsk en Sotsji