De stad werd in 1789 gesticht door de Russische gouverneur-generaal van Novorossija Knyaz Potemkin, aanvankelijk als een scheepswerf, eenvoudigweg Nieuwe Scheepswerf genoemd, aan de rivier de Ingul. Knyaz Potemkin tekende een order om een scheepswerf te bouwen op 27 augustus 1789, wat beschouwd wordt als de geboortedatum van de stad. De scheepswerf moest dienen voor de reparatie van de Russische marineschepen in de Russisch-Turkse oorlog. Later gaf Potemkin opdracht de scheepswerf Nikolajev te noemen om de datum te herdenken van de val van Ochakov voor de Russische troepen onder zijn bevel op 6 december 1788, dicht bij de dag van de Heilige Nicolaas (Nikolaj) 19 december, in de Russisch-orthodoxekerk.
De geschiedenis van de stad is altijd nauw verbonden geweest met de scheepsbouw.
Het enige vliegdekschip van de Russische marine dat momenteel in gebruik is, Admiral Flota Sovetskogo Soyuza Kuznetsov, is gebouwd in Mykolaiv.