На все четыре крейсера были установлены по две батареи малокалиберных 30-мм автоматов АК-630 с системой управления огнем «Вымпел» у каждой.

Противокорабельные крылатые ракеты (ПКР) 4К44 в 1982 г. были заменены на ПКР «Прогресс». Комплекс «Прогресс» был модернизацией комплекса П-35 с целью повышения боевой эффективности за счет совершенствования системы управления при сохранении внешнего облика, габаритов и основных систем ракеты.

Крейсера пр.58 несли службу в составе всех четырех флотов. На них не происходило серьезных аварий, что дает основание заключить, что корабли оказались надежными и доступными для эксплуатации.

Первым из состава флота был исключен РКР «Варяг» приказом от 29.04.1990. За ним последовал «Грозный», исключенный из состава флота 31.12.1992. До этого он два года ремонтировался на заводе «Тосмаре» в Лиепае. Летом 1992 г. он был выведен из сухого дока завода и стоял у стенки большой (летней) гавани порта. В море его не выпускали латвийские власти, так как моряки не оплатили все затраты по ремонту крейсера заводом. Во время первого же шторма в октябре крейсер «Грозный» разбился о стенку и затонул прямо в гавани. Был брошен моряками во время «великого драпа», став памятником-напоминанием латышам о пребывании советского Военно-Морского Флота в Латвии. Правда, далеко не он один.

РКР «Адмирал Фокин» был исключен из списков флота 30.06.1993.

Долгожителем оказался РКР «Адмирал Головко», базируясь на Севастополь, он дожил до конца 2002 г. и был исключен из списков флота в конце декабря.

Так закончилась история первых советских ракетных крейсеров.

30 декабря 1959 г. произошло знаменательное событие. В состав ВМС США была принята атомная ПЛ «Джордж Вашингтон» с 16 баллистическими ракетами на борту. 15 ноября 1960 года она вышла в свой первый поход. БР «Поларис А1» с ядерными боезарядами могли стартовать из-под воды и имели дальность 2200 км, что позволяло им из Средиземного моря и Северной Атлантики поражать стратегические объекты в Европейской части СССР.

Это заставило военно-политическое руководство страны задуматься об организации эффективного противодействия этим ракетоносцам. Требовалось обнаружить и уничтожить вражескую подводную лодку до того момента, как она осуществит запуск ракет. Следовало построить эшелонированную систему противолодочной обороны (ПЛО). Картина использования противолодочных сил в тот период выглядела следующим образом. Дальняя зона ПЛО начиналась на расстоянии 150 миль от нашего побережья. Границы зоны определялись как радиусом действия существовавших у нас противолодочных кораблей, так и тактическим радиусом противолодочной и истребительной авиации берегового базирования.

Оборона дальних противолодочных рубежей возлагалась на подводные лодки и береговую авиацию ПЛО дальнего действия. В сложившейся ситуации этого было уже недостаточно. Необходимы были корабли дальней зоны ПЛО. Так как предполагалось несение этими кораблями службы вне районов, контролируемых нашей береговой авиацией, то при отсутствии у нас авианосцев им была необходима обязательная поддержка специальными кораблями ПВО, которые планировалось вооружать кроме средств самообороны ЗРК дальнего действия, способными обеспечить эшелонированную оборону поисково-ударного противолодочного соединения от современных средств воздушного нападения.

В программу военного кораблестроения на 1959-1965 гг. было включено создание ракетного корабля ПВО. Он должен был включаться как флагманский (обеспечивающий централизованное управление средствами ПВО) в состав поисково-ударных групп, предназначавшихся для борьбы с атомными подводными ракетоносцами противника. Тем самым предпринималась очередная попытка обеспечения ПВО групп наших кораблей в океане без создания авианосцев.

Постановлением правительства от 25 июля 1959 г. были определены основные элементы корабля ПВО пр. 1126 и его вооружение, основой которого должен был стать зенитный ракетный комплекс большой дальности М-31. На корабле предусматривалось два ЗРК М-31, два универсальных ЗРК средней дальности М-11, две (затем четыре) двуствольные 57-мм артустановки, два трехтрубных торпедных аппарата для противолодочных торпед, две РБУ-1000 («Смерч-3»), соответствующее радиолокационное вооружение, включая систему наведения истребительной авиации. Стандартное водоизмещение ограничивалось 10000 т. Скорость 33-34 узла, дальность плавания 24-узловым ходом 5000 миль. Работа была поручена ЦКБ-17. Главный конструктор вначале В.В. Ашик, с 1960 г. — П.П. Милованов. По своим размерам и составу вооружения это был, конечно, крейсер ПВО с некоторыми элементами нападения, так как комплекс М-11 был универсальным и мог стрелять по надводным целям.

В эскизном проекте было проработано 20 вариантов корабля с различными материалами корпуса корабля, энергетической установки, водоизмещением от 6200 до 11100 т, максимальной скоростью от 29,7 до 35,5 уз. Эскизный проект был утвержден в июле 1960 г. Для дальнейшего проектирования рекомендовался вариант стандартным водоизмещением 9000 т с двумя котлотурбинными установками мощностью 2x45000 л.с. (по пр. 58).

Однако, в том же в 1960 г. в начале было принято решение о сокращении числа намеченных к постройке кораблей пр. 1126 с трех до двух, а в 1961 г. разработка технического проекта была прекращена, крейсера были исключены из кораблестроительной программы.

Объективное рассмотрение проблемы ПВО привело к однозначному выводу: с учетом быстрого развития средств воздушного нападения вероятного противника ни уже разработанные, ни перспективные корабельные ЗРК не в состоянии с требуемой вероятностью гарантировать неуязвимость соединения, а тем более одиночного корабля. Только барражирующая палубная истребительная авиация могла обеспечить дальнюю ПВО, позволяя тем самым создать минимальный резерв времени для успешного использования зенитного ракетного комплекса.

Но поскольку такие выводы были неудобны для официальной точки зрения, то всем «умникам» было приказано молчать и «сопеть в тряпочку». Так наш флот на все обозримое пространство остался без прикрытия с воздуха.

Следующий наш ракетный крейсер появился тоже случайно. Планом военного кораблестроения на 1959—1965 гг. для ПЛО в дальней зоне предусматривались вертолетоносцы пр. 1123. Для их охранения нужен был корабль, на который бы возлагались и другие оперативные возможности.

Тактико-техническое задание на него было выдано в 1961 г. Основным назначением корабля являлись: защита своих морских сообщений от воздушных, надводных и подводных сил противника, обеспечение кораблей ПЛО, действующих в удаленных районах моря, обеспечение боевой деятельности подводных лодок. Из назначения корабля явно просматривалась роль противовоздушного и противолодочного вооружения.

Разработкой проекта занималось ЦКБ-53, получившее ТТЗ в декабре 1961 г. Главным конструктором был назначен В.Ф. Аникиев. Разработка началась сразу с технического проекта, так как предполагалось создать новый корабль в корпусе ракетного крейсера пр.58. Основным оружием корабля должен был стать новый ЗРК М-11 «Шторм», а основным противолодочным оружием — ракетный комплекс «Метель». Комплекс «Шторм» уже был в разработке, а вот к комплексу «Метель» еще толком и не приступали, поэтому его на первых корпусах сразу же решено было заменить на П-35. Так и получился очередной ракетный крейсер.