Do 1965 weszły do służby kolejne 3 okręty: "Admirał Fokin", "Admirał Gołowko" i "Wariag". Wszystkie budowano w stoczni im. A.A. Żdanowa w Leningradzie. Początkowo planowano 10-16 jednostek, lecz zrezygnowano z budowy dalszychJ. Radziemski, Saga..., s. 4-11.
NazwaPołożenie stępkiWodowanieWejście do służbyWycofanieGroznyj (Грозный)23.02.196026.03.196130.12.196224.6.1991Admirał Fokin (Адмирал Фокин)5.10.196019.11.196128.12.196430.6.1993Admirał Gołowko (Адмирал Головко)20.04.196118.7.196230.12.1964 2002Wariag (Варяг)5.08.19617.04.196320.08.196519.04.1990
thumb|"Wariag" od rufy, 1989 rok thumb|"Admirał Gołowko", 1990 rok
Konstrukcja Okręty proj. 58 wykonano ze stali, lecz z dużym wykorzystaniem stopów lekkich. Kadłub otrzymał linię ocenianą jako ładną, z uskokiem rufowym na 2/3 długości; podzielono go na 17 przedziałów wodoszczelnych. Okręty te wprowadzały wiele nowości w radzieckiej architekturze okrętów, w tym niskie nadbudówki i duże, masywne maszty, mieszczące w środku część pomieszczeń. Najbardziej rzucającymi się w oczy elementami i głównym elementem uzbrojenia krążowników były dwie duże czterokontenerowe wyrzutnie pocisków przeciwokrętowych dalekiego zasięgu P-35 na dziobie i rufie. Pociski te mogły zwalczać cele nawodne lub brzegowe.