В середине 70-х гг. НПО Машиностроения был создан комплекс «Базальт» с ПКР П-500. Ракета имела массу около 6 тонн, дальность стрельбы 550 км, обычную (500 кг) или ядерную боевую часть, сложную траекторию полета и скорость, в два раза превосходящую скорость звука. Комплекс Базальт располагал усовершенствованной системой распределения целей между восемью ракетами одного залпа и оптимизированным алгоритмом выбора главной цели в ордере АУГ.

На ПКР П-500 была впервые установлена система РЭП, обеспечивающая защиту от средств ПВО АУГ. Целеуказание Базальта обеспечивалось созданной к этому времени системой МКРЦ «Легенда» (на вооружении с 1976 г.) и самолетами Ту-95РЦ. Носителями крылатых ракет, среди прочих, должны были стать новые ракетные крейсера, способные применить в одном залпе 16 ПКР, что по боевой эффективности в четыре раза превосходило возможности существующих на то время РКР. Разработка проекта была поручена Северному ПКБ. Головной РКР серии из шести первых в СССР крейсеров с газотурбинными установками проекта 1164 под кодовым названием «Атлант» заложен на стапеле Николаевского судостроительного завода им. 61 коммунара 4 ноября 1976 г. Корабль, получивший имя «Слава», был спущен на воду 27 июля 1979 г., через год произошло заселение экипажа, вступил в строй в конце 1982 года, а в феврале следующего года включен в состав Краснознаменного ЧФ.

Название «Слава» в истории русского флота носили несколько кораблей. Это 16-пушечный фрегат, отличившийся в войне 1768-1774 гг. с Турцией; в конце XVIII в. его сменил 38-пушечный фрегат, охранявший воды Балтики, а в годы 1-й мировой войны с кораблями германского флота сражался линейный корабль Слава. В 1978 г. был заложен, в апреле 82-го спущен на воду и 21 сентября 1986 г. передан в состав СФ второй РКР серии — «Маршал Устинов». 17 декабря 1997 г. на нем закончился плановый ремонт, затянувшийся на три года. На петербургском АО «Северная верфь» крейсер, в числе прочего, получил новую ГЭУ. 24 февраля 2001 г. над крейсером взяла шефство столица Белоруссии. Юридически этот факт был закреплен договором, который подписали председатель Минского горисполкома и командир корабля. В 1979 г. был заложен, 28 июля 83-го спущен на воду и 16 октября 1989 г. вступил в строй крейсер «Червона Украина». Первоначально, этот корабль, как и «Слава», попал в 150-ю БРНК, где они до 1990 г. представляли главную ударную силу Краснознаменного ЧФ, после раздела которого, в 1996 г. Россия дала крейсеру не менее прославленное имя «Варяг» и перевела его на ТОФ.

В июле 1989 г. на крейсере Слава проводился советско-американский эксперимент по возможности дистанционного обнаружения ядерных КРМБ. Американская группа участников использовала прибор с полупроводниковым детектором гамма-излучения на основе кристалла высокочистого германия с энергетическим разрешением около 2 кэв. Детектор размещался непосредственно на ПУ «убийцы авианосцев» (такое прозвище получили крейсера проекта 1164 на Западе). Полученный в течение 10 минут спектр излучений с пиковыми значениями, характерными для различных изотопов урана, плутония и некоторых продуктов их распада, подтверждал наличие ядерной боеголовки. При этом результаты измерений показали, что таким путём практически нельзя получить дополнительную информацию о конструкции боеголовки, что устраивало обе стороны.В начале декабря 1989 г. ракетный крейсер «Слава» принимал участие в обеспечении первой втречи Генерального секретаря Компартии СССР Михаила Горбачева с президентом США Джорджем Бушем на о. Мальта. В 90-м «Славу» поставили на стапеля Николаевского завода для частичной модернизации. Плановые восемь месяцев превратились в долгие восемь с половиной лет. Финансирование не поступало вообще, и первые пять лет крейсер сохранялся только благодаря самоотверженности экипажа. Только шефская помощь столичной мэрии и лично Юрия Лужкова позволили найти средства для окончания ремонта.
Без действенной и всесторонней помощи москвичей, активной и принципиальной позиции командующих ЧФ адмиралов Игоря Касатонова, Виктора Кравченко и Владимира Комоедова корабль, наверное, и по сей день продолжал бы оставаться неподвижным памятником былому могуществу советского флота. 22 июня 1995 г. приказом Главнокомандующего ВМФ РФ крейсер получил новое имя — «Москва». 12 июня 1997 г. на корабле был поднят Андреевский флаг. 13 мая 1998 г. с целью сохранения на флоте гвардейских традиций кораблю переданы флаг и гвардейское звание от выводимого из состава ЧФ гвардейского сторожевого корабля «Красный Кавказ». 19 июля 1999 г., после нескольких переносов времени выхода, «Москва» наконец покинула Николаев. В районе Очакова крейсер приняли уже наши флотские буксиры, и спустя три дня, 21 июля, корабль известил вечерний Севастополь о своем возвращении залпами салютных пушек. 25 июля, в День ВМФ России, флагман ЧФ России стоял в парадном строю в Севастопольской бухте. В апреле 2000 г. впервые за 10 лет «Москва» вышла в море для проверки ходовых механизмов. После проверки оружия, в ноябре крейсер вошел в состав сил постоянной готовности. Сегодня командиром РКР «Москва» является капитан I ранга Валерий Владимирович Куликов.

Последний, четвертый, корабль серии был заложен летом 1984 г. под именем «Адмирал флота Лобов». Спуск на воду состоялся 1 августа 1990 г. 18 марта 1993 г. при 75-процентной готовности Россия отказалась его достраивать, аргументируя это тем, что в составе ее флота есть аналогичный крейсер «Москва», а также невозможностью изыскать средства на достройку корабля. 1 октября 1993 г. крейсер перешел в собственность Украины. Предложение Украины о продаже крейсера третьей стране (его стоимость, по разным оценкам, составляет от 450 до 700 млн. дол.), вызвали протест со стороны России, поскольку в строительстве корабля и его вооружении использованы секретные технологии советского ВПК. Корабль несколько лет простоял без обслуживания и отопления в зимнее время неоднократно подвергаясь «рейдам» мародеров-искателей цветного металла. Наконец, 17 февраля 1998 г. Президент Украины принял официальное решение о переименовании крейсера о его достройке для украинских ВМС, причем в проектном варианте. При самом благоприятном стечении обстоятельств РКР «Украина» вступит в строй в 2001 году.