Nowy okręt miał być również dostosowany do przenoszenia nowo opracowywanych ponaddźwiękowych myśliwców Jak-41 (Jak-141), których rozwoju jednak nie zakończono.
Stępkę pod budowę okrętu położono 26 grudnia 1978 roku w stoczni Czarnomorskiej (nr 444) w Mikołajowie (numer stoczniowy S-104), tuż po wodowaniu „Noworossijska”. Już 17 lutego 1978 został on wciągnięty na listę floty, pod nazwą „Baku” (od stolicy radzieckiej republiki Azerbejdżanu), noszoną wcześniej przez niszczyciel z okresu II wojny światowej. Budowa odbywała się na największej pochylni „0”, metodą blokową, z sekcji o masie do 150 ton. Po wyposażeniu stoczni w nowe dźwigi fińskiej firmy Kone, zamontowano nadbudówkę, o masie 1000 ton, w całości. Kadłub wodowano 31 marca 1982 roku (miał wówczas masę ok. 19 000 t). Wyposażanie trwało dość długo na skutek zmian wprowadzanych w konstrukcji i problemów z dostawami nowych systemów i dopiero od stycznia 1987 roku okręt przechodził oficjalne , a od 21 kwietnia 1987 odbiorcze próby państwowe. 11 grudnia 1987 okręt przyjęto do służby w Marynarce ZSRR.