Ostatecznie tylko „Admirał Nachimow” został ukończony według pierwotnego projektu, jako „Czerwona Ukraina”, natomiast „Admirał Łazariew” został przeprojektowany (jako „Krasnyj Kawkaz”), a z budowy pozostałych dwóch zrezygnowano.
Stępkę pod budowę „Admirała Nachimowa” położono 19 października 1913 roku w stoczni Russud w Mikołajowie na Ukrainie, wraz z bliźniaczym „Admirałem Łazariewem” (1 listopada nowego stylu – daty sprzed 1918 roku podane w starym stylu). Faktycznie budowę rozpoczęto jednak dopiero w lipcu 1914 roku.. Oficjalne zamówienie na budowę okrętu zostało złożone w stoczni Russud 11 marca 1914 roku, z terminem ukończenia określonym na 20 października 1916 roku. Urządzenia napędowe miała wykonać stocznia OZNiW w Mikołajowie. Początkowo prace przy kadłubie przebiegały sprawnie i wodowano go 24 października (6 listopada nowego stylu) 1915 roku, lecz na etapie wyposażania wystąpiły opóźnienia z powodu trudności wojennych i konieczności sprowadzenia elementów turbin z Wielkiej Brytanii. Nowy termin oddania okrętu przewidziano na marzec, a następnie lipiec 1917 roku, lecz również nie został on dotrzymany, a dalsze opóźnienia budowy wywołała rewolucyjna sytuacja wewnętrzna w Rosji.