Головной корабль в заданной семилетним планом серии из 16 кораблей. «Грозный», был заложен на ленинградском «Ждановском заводе» (№ 190) 23 февраля 1960 г. Через год с небольшим, 26 марта, его спустили на воду. Настоящий аврал на достройке корабля начался после принятия решения о посещении Северного флота «нашим Никитой Сергеевичем». Все, что не успели доделать на берегах Невы, «доводили до ума» в Кольском заливе. «Грозный» принял участие в наиболее эффектной части программы – демонстрации ракетных стрельб новых кораблей. Ради повышения престижа и материального обеспечения офицеров отлично «отстрелявшегося» «Грозного» обрадованный Хрущев с подачи С.Г Горшкова даже одобрил переклассификацию эсминца пр. 58 в «ракетные крейсера». Видимо, ему пришлось преодолеть внутреннее отвращение к термину «крейсер», сформировавшееся за годы эпопеи с попытками как-то пристроить недостроенные корабли пр. 68бис-ЗиФ.
В результате остальные три корабля пр. 58, сданные флоту с 28 ноября 1964 г. по 20 июля 1965 г. и строившиеся под заводскими номерами 782, 783 и 784, с 30 октября 1962 г. вместо «имен прилагательных», принятых еще с царских времен для наименования эсминцев, удостоились славных имен «Адмирал Фокин» (бывший «Стерегущий», а до 11 мая 1964 г. – «Владивосток»), «Адмирал Головко» (вместо «Доблестный») и «Варяг» (ранее «Сообразительный»), Только уже вступивший в строй «Грозный» (заводской номер 781) сохранил традиционное для эсминца наименование. Этому первенцу ракетных крейсеров довелось вскоре вернуться на завод-строитель для проведения ряда доработок, а летом 1965 г. он был впервые продемонстрирован простым советским людям во время традиционного парада на Неве. Иностранцам, интересующимся нашим флотом в силу своих служебных обязанностей, он стал известен намного раньше – при переходе на Север в 1962 г.
Исключительно эффектный и современный вид ракетных крейсеров пр. 58 способствовал их активному привлечению к официальным визитам в зарубежные страны. Этот корабль стал главным героем художественных фильмов «Нейтральные воды» и «Визит вежливости».
Проект 1134
Явная слабость оборонительных возможностей корабля пр. 58 была очевидна задолго до его достройки. Поэтому постановлением от 7 июля 1962 г. правительство ограничило их постройку в ходе семилетки четырьмя единицами, предусмотрев дополнительно постройку трех кораблей пр. 1134.
Ранее постановлением от 30 декабря 1961 г. задавалась разработка в 1962 г. технического проекта корабля «с усиленным противолодочным и противовоздушным вооружением» по пр. 1134. Основной идеей нового проекта было совмещение в одном корабле боевых возможностей уже упомянутой тройки из ракетного крейсера пр. 58 и двух БПК пр. 61. Стоимость одного такого корабля, хотя и превышала показатели ранее разработанных проектов, была многократно меньше затрат на постройку трех кораблей.
Предварительные проектные проработки, выполненные в ЦКБ-53 под руководством В.Ф. Аникеева, показали принципиальную решаемость поставленной задачи с использованием корпуса пр. 58 при превышении водоизмещения всего на 200-300 т. Правда, при этом предусматривалось основательное снижение ударной ракетной мощи до 4-6 ракет П-35, уменьшение калибра артиллерии до 57 мм. Наиболее предпочтительным оказался вариант с бортовым размещение П-35 в шести одиночных поднимаемых контейнерных пусковых установках.
Для противовоздушной обороны корабля планировался предназначенный для противолодочного крейсера пр. 1123 новый комплекс М-11 «Шторм» с максимальной дальностью, вдвое превышавшей возможности М-1. В качестве основы самообороны предполагался комплекс «Оса-М». Но разработка этих средств затягивалась. Исходя из этого в соответствии с упомянутым постановлением 1961 г. допускалась возможность оснащение первых кораблей пр. 1134 оружием от пр. 58 и 61. Но при этом вместо одного комплекса «Волна» устанавливались два, пусковые установки ЗиФ-101 заменялись на ЗиФ-102 с более емкой конвейерной подачей ракет вместо барабанной. Огневая производительность удвоилась, а общий боекомплект возрос вчетверо, составив 64 ракеты, что как раз соответствовало входившим в «тройку» двум ВПК пр. 61. Как и на этих ВПК, пусковые установки и станции наведения ракет «Ятаган» размещались как в сторону носа, так и кормы, исключая непростреливаемые углы. Поняв, что безангарное базирование вертолета на относительно небольшом корабле скорее аттракцион, чем боевое применение, пр. 1134 оснастили стационарным ангаром.