После проведения полного цикла испытаний ракетный крейсер «Грозный» вступил в строй 30 декабря 1962 г., сохранив свое прежде название.
РКР «Стерегущий», заложенный 5 октября 1960 г. и спущенный на воду 19 ноября 1961 г., успев побывать «Владивостоком» (с 10.10.1962 по 11.05.1964) был введен в строй 28 декабря 1964 г. под названием «Адмирал Фокин».
РКР «Доблестный», заложенный 20 апреля 1961 г. и спущенный на воду 18 июля 1963 г., получил 18.12.1962 имя «Адмирал Головко». Введен в строй 30 декабря 1964 г.
РКР «Сообразительный», заложенный 13 октября 1961 г. и спущенный на воду 7 апреля 1963 г., уже с 31.10.1962 носил имя «Варяг». Введен в строй 20 августа 1965 г.
Водоизмещение корабля: стандартное 4350 т, полное — 5400 т. Размеры 142,7x16x5 м. Энергоустановка котлотурбинная 2x45000 л.с. Скорость полного хода 34,5 уз. Дальность плавания скоростью 14,3 уз — 4500 миль. Автономность — 10 суток. Экипаж — 300 человек.
Корабль оснащен противокорабельным комплексом П-35 с двумя счетверенными пусковыми установками СМ-70, обеспечивающими горизонтальное наведение. Старт ракет осуществлялся при фиксированном возвышении в 25 градусов. Трубы пусковых установок являлись штатным местом для хранения заправленных топливом ракет. В них постоянно размещались восемь ракет 4К44. Кроме того имелись еще восемь ракет в погребах, расположенных в надстройках. Они хранились в незаправленном состоянии. Две ракеты имели «спецзаряд» (ядерный). Система управления «Бином» с двумя антенными постами находилась на башенноподобных мачтах и позволяла осуществлять одновременно двухракетный залп из каждой ПУ. Суммарный залп тем самым состоял из четырех ракет. Время подготовки первого залпа составляло 12 мин. В дальнейшем, после доработки и усовершенствования всей системы управления, залп мог осуществляться восемью ракетами. На перезарядку пусковой установки уходило несколько часов. Это в идеале. Так как из-за массы ограничений и трудностей в море эту работу никогда не производили, а все делалось только в базе у стенки. Тем не менее, крейсер пр. 58 был первым надводным носителем ядерного оружия в советском флоте.
ЗРК «Волна» размещался в носовой части. В состав комплекса М-1 «Волна» входили спаренная стабилизированная ПУ ЗИФ-101, система хранения и подачи ЗУР В-600 (4К90) и система управления ракет 4Р90 «Ятаган». В погребе в двух револьверных барабанах размещались 16 ракет (2x8). Боевые характеристики комплекса обеспечивали два пуска каждые 5 сек. Дальность стрельбы составляла 15 км. Досягаемость по высоте —10 км. Минимальная высота поражения — 100 м и зависела от скорости цели.
В середине 60-х годов моряки научились стрелять комплексом М-1 по надводным целям, он стал считаться универсальным и был любим моряками, так как время его реакции было на порядок меньше, чем у громоздких П-35. Но это только для ближнего боя. Все-таки П-35 имел дальность до 300 км.
В 1967 г. комплекс М-1 получил новые ракеты В-601 (4К91). Максимальная дальность увеличилась до 22 км, высота — до 14 км. В последующем, когда возникла проблема защиты кораблей от низколетящих противокорабельных ракет, была проведена еще одна модернизация. Доработанный комплекс получил индекс «Волна-Н». Ракета В-601М обеспечивала поражение цели на высоте 3—5 метров над гребнем волны.
В кормовой части корабля находились две спаренные 76-мм универсальные АУ АК-726 (ЗИФ-67) с системой управления стрельбой РАС «Турель». Скорострельность установки — 90 выстрелов в минуту. Поскольку станция «Турель» (МР-105) была одна на два орудия, то обе башни превращались как бы в одну четырехорудийную.
Главным предназначением АУ АК-726 была противовоздушная оборона. По выработанной на десятилетия вперед концепции в системе ПВО артиллерия достреливала цели, которые не смогли сбить зенитные ракеты (если они вообще участвовали в этом мероприятии). Время реакции определяли подбор артиллерии, ее калибр, в зависимости от дальности действия ЗУР. Образовывались своеобразные пары.
Недооценка ствольной артиллерии была не в этом, как пишут многие «светлые умы», но об этом далее. Просто нужно было определить ее роль.
Целеуказание средствам ПВО обеспечивалось от двух РАС «Ангара» (МР-300).
Противолодочное вооружение включало два трехтрубных торпедных аппарата ТТА-53-57бис, которые размещались побортно на верхней палубе и предназначались для стрельбы самонаводящимися торпедами СЭТ и дальноходными торпедами 53-57.
Имелись также две РБУ-6000 (реактивные бомбометные установки) с глубинными бомбами РГБ-60. Установка двенадцатиствольная с автоматической перезарядкой. Запас 96 бомб. Управление стрельбой — с помощью системы «Буря». Комплекс РБУ-6000 использовался и для противоторпедной защиты.
Целеуказание для торпед и бомб обеспечивалось гидроакустической станцией «Геркулес-2М».
Авиационное вооружение на крейсере было чисто символическим, так как при таком водоизмещении не удалось установить ангар для вертолета Ка-25. Поэтому на пр. 58 была лишь взлетно-посадочная площадка со светотехническим оборудованием, стартово-командный пост и запас керосина в 5 тонн. Сам вертолет принимался в перегруз и базировался на берегу.
За основу теоретического чертежа корпуса был выбран теоретический чертеж пр.56, так как он прошел тщательную и всестороннюю проверку теорией и практикой. В качестве материала корпуса была выбрана сталь марки СХЛ-4. Надстройки в основном выполнялись из алюминиево-магниевых сплавов марок АМГ-5В и 6Т (что было не очень хорошо, как показал впоследствии Фолклендский кризис), только передняя стенка носовой и задняя стенка кормовой надстроек, два яруса фок-мачты, башенная часть грот-мачты, а также подкрепления под антенные посты РАС «Ятаган» и «Турель» выполнили из стали. АМГ использовался также для легких переборок, площадок, настилов, тамбуров и шахт. Противоосколочная защита погребов была отвергнута по соображениям экономии весов. Эта же причина обусловила широкое применение АМГ.
Общий вид корабля, по сравнению с ранее построенными, отличался размещением главного командного пункта в корпусе, отсутствием открытых боевых постов, проходом в посты без выхода на верхнюю палубу.
Главная энергетическая установка корабля принималась в основном по предыдущим проектам 41, 56, 576ис. Но для достижения скорости хода в 34,5 узла потребовалось форсирование котлов и турбозубчатых агрегатов при сохранении требований жесткой весовой дисциплины и экономичности.
Выдвигались особые требования по защите от оружия массового поражения (герметичность, внутренний наддув, омывание надстроек и корпуса и т.д.).
Штатным расписанием предусматривалось 27 офицеров, 29 мичманов и главстаршин, 283 старшины и матроса срочной службы.
На рубеже 70-80-х годов корабли подверглись частичной модернизации. На них установили часть положенного недостающего радиотехнического вооружения. Систему «Успех-У» установили только на крейсера «Адмирал Фокин» и «Грозный». На «Варяге» и «Фокине» двухкоординатные РАС МР-300 заменили на трехкоординатные МР-310. На всех кораблях появилась вторая РАС обнаружения надводных целей «Дон-2», салютные пушки (правда, они были размещены в разных местах).
На все четыре крейсера были установлены по две батареи малокалиберных 30-мм автоматов АК-630 с системой управления огнем «Вымпел» у каждой.
Противокорабельные крылатые ракеты (ПКР) 4К44 в 1982 г. были заменены на ПКР «Прогресс». Комплекс «Прогресс» был модернизацией комплекса П-35 с целью повышения боевой эффективности за счет совершенствования системы управления при сохранении внешнего облика, габаритов и основных систем ракеты.