In de [[Klassiekeklassieke Oudheidoudheid]] warenlag de kusten vanaan de [[Baai van Tsemess]] de plaats ''Bata'', een oude [[Griekse kolonisatie|Griekse kolonie]] die zich in de graanhandel specialiseerde. De plaats wordt vermeld in werken vandoor onder andere [[Strabo (historicus)|Strabo]] en [[Claudius Ptolemaeus]].
Op de plek waar nu Novorossiejsk ligt bevond zich in de [[13e eeuw|13e]] en [[14e eeuw]] een [[Republiek Genua|Genuese]] [[Kolonisatie en imperialisme (staatkunde)|kolonie]]. In 1722 verscheenwerd er een [[Ottomaanse Rijk|Ottomaanse]] vesting gebouwd, die in 1808 door het [[Keizerrijk Rusland|Russische Rijk]] veroverd werd. De stad werd gesticht in [[1838]] gesticht als [[Marine (strijdmacht)|marine]]basis.
Tijdens de [[Russische Burgeroorlog]] was Novorossiejsk een bastion van de [[Witten (leger)|Witten]], totdat de [[Bolsjewiek]]en de stad op 27 maart 1920 veroverden. In 1942 werd Novorossiejsk bezet door de [[Wehrmacht]], maar een kleine eenheid van de [[Marine van de Sovjet-Unie|SovjetRode Vloot]]-marine met [[Leonid Brezjnev]] wist een deel van de stad in handen te houden, zodat de Duitse troepen geen gebruik konden maken van de haven. Gedurende 225 dagen hielden de Sovjets stand in de [[heldenstad]] en op 16 september 1943 werd Novorossiejsk bevrijd door het [[Rode Leger (Sovjet-Unie)|Rode Leger]].
