Поэтому разработку новой, более совершенной ракеты Р-21 комплекса Д-4, способной стартовать из-под воды, поручили конструкторскому бюро Михаила Кузьмича Янгеля (1911—1971). Но вскоре решение переиграли, и разработкой комплекса вновь занялся коллектив Макеева. Конструкторов всё время подгоняли — в США уже заканчивалась подготовка к испытаниям аналогичной ракеты «Polaris» — нужно было любой ценой обогнать ненавистных «янки».
Несмотря на все старания, заочное соревнование ракетчиков и кораблестроителей закончилось победой американцев. 20 июля 1960 года впервые в мире с борта атомной подводной лодки «George Washington», находившейся на глубине 30 метров, был произведён пуск ракеты «Polaris» (она пролетела 1800 км). Через сорок дней (этот траурный срок в данном случае весьма символичен) — 10 сентября 1960 года — с подводной лодки Б-67 из подводного положения стартовала ракета С4.7 (доработанная Р-11ФМ), пролетевшая всего-навсего 125 км. Явно намечалось серьёзное отставание от США, смириться с которым в Кремле не хотели.
Для максимального ускорения работ над Р-21 решили объединить в один все этапы испытаний (лётно-конструкторские, промышленности, ВМФ). Наконец, 24 февраля 1962 года с подводной лодки К-142 проекта 629Б был произведён первый пуск ракеты Р-21 из подводного положения. По итогам ускоренных испытаний комплекс Д-4 приняли на вооружение ВМФ 15 мая 1963 г.
Атомная подводная лодка К-19 пр. 658M («Hotel»)
Пуск ракеты Р-21 с подводной лодки С-229, находящейся под водой
Первыми их получили атомные лодки проекта 658. Головная К-19 и последующие семь лодок, достроенные по проекту 658М, сначала несли на своем борту ракеты Р-13. В 1965—70 гг. они прошли модернизацию, получив ракетный комплекс Д-4 с тремя ракетами Р-21. Теперь запуск ракет мог производиться из подводного положения с глубины до 60 метров, при скорости лодки до 4 узлов и волнении моря до 5 баллов.
Перед пуском ракеты шахту заполняли водой, после чего открывали крышку шахты и включали маршевый двигатель. После пуска требовалось принять в уравнительную цистерну около 15 кубометров воды, иначе лодка всплывала на 16 метров вверх.
Комплексом Д-4 стали оснащать также и дизельные подводные лодки проекта 629, но их модернизация и перевооружение затянулись на девять лет — до 1972 года (!).
Максимальная дальность полёта ракеты Р-21 составляла 1420 км, а круговое вероятное отклонение — три километра. Недостаточную точность стрельбы компенсировала увеличенная мощность ядерной боеголовки. Всего до 1982 года в процессе эксплуатации были запущены 228 ракет. Из этого числа 193 пуска (85%) признали успешными.
Подводные лодки проектов 658 и 658М стали первыми атомными стратегическими ракетоносцами советского флота и несли боевую службу до конца 80-х годов, несмотря на то, что морально они устарели ещё до вступления в строй. Они вошли в состав сформированной в 1961 году 31-й дивизии подводных лодок Северного флота.
Их боевая ценность, ввиду ограниченной дальности и низкой точности попадания ракет, была невысокой. Более того, головная лодка серии К-19 заслужила в советском ВМФ печальное прозвище «Хиросима», поскольку весь срок службы её преследовали аварии с многочисленными человеческими жертвами.
Наиболее уязвимым местом первых советских атомных подводных лодок являлась крайне несовершенная энергетическая установка. Неотработанная конструкция атомных реакторов постоянно преподносила трагические сюрпризы. Так, 13 октября 1960 г. произошла авария атомного реактора на подводной лодке К-8, которую удалось ликвидировать с минимальными потерями. Прошло чуть более полугода, как на той же лодке случилось новое происшествие — утечка радиоактивного газа. Через два года на К-11 произошёл пуск реактора с мгновенным выходом на неконтролируемый уровень мощности и с выбросом радиоактивного пара, после чего начался пожар в реакторном отсеке. Подобные происшествия регулярно случались и на других подводных лодках.
Все попытки конструкторов и производственников устранить их особого эффекта не давали. Дело дошло до того, что группа офицеров-подводников отдельной бригады подводных лодок Северного флота, служившие на первых атомоходах, обратилась с жалобой в ЦК КПСС. Они информировали партийное руководство о том, что «имеющиеся в строю и строящиеся атомные подводные лодки в настоящее время не пригодны к боевому использованию по линии энергетики».