Хотя все отечественные ПЛАРБ Атомная подводная лодка с баллистическими ракетами первого поколения оснащались исключительно жидкостными ракетами (что соответствовало реальному уровню советского ракетостроения) , флот и специалисты промышленности прекрасно осознавали все эксплуатационные недостатки таких ракет. БР Баллистическая ракета с ЖРД Жидкостно-реактивный двигатель обладали высокой токсичностью и пожаро-взрывоопасностью. Специфика их применения требовала при осуществлении подводного старта предварительного заполнения забортной водой кольцевого зазора шахт, для чего создавалась сложная система трубопроводов и насосов. В результате перекачивания больших объемов воды в период предстартовой подготовки повышался уровень шумов, демаскирующих подводную лодку. Все эти недостатки отсутствовали у ракетных комплексов с твердотопливными ракетами. Поэтому параллельно с созданием жидкостных морских БР Баллистическая ракета в нашей стране в конце 50-х годов начались работы и над первыми твердотопливными ракетами для оснащения подводных лодок.
В соответствии с правительственным постановлением от 9 сентября 1958 г. ленинградское КБ «Арсенал» приступило к разработке ракетного комплекса Д-6 с твердотопливной ракетой, предназначенного для оснащения перспективных ракетоносцев. Работы велись по двум параллельным направлениям — созданию БР Баллистическая ракета с двигателем на баллистных порохах, а также на более перспективном смесевом топливе. Недостатком первого варианта являлась необходимость использования громоздкой связки из четырех двигателей, что приводило к чрезмерному росту габаритов ракеты, а создание двигателя на смесевом топливе требовало решения ряда сложных научных, технических и технологических задач, которые на рубеже 50 — 60-х гг. оказались еще «не по плечу» отечественному ракетостроению. Возник и ряд чисто организационных трудностей. В результате в соответствии с постановлением от 4 апреля 1961 г. работы по программе Д-6 были прекращены.
Тем же правительственным постановлением ОКБ Опытно-конструкторское бюро В. П. Макеева поручалось приступить к работам по новому твердо-топливному «лодочному» комплексу Д-7 с ракетой РТ-15М (4К-22), ориентированному на новую подводную лодку 667-го проекта. При этом вся техническая документация, разработанная «арсенальцами» по программе Д-6, была передана в СКБ-385.
Ракета РТ-15М должна была иметь стартовую массу порядка 50 т (более чем в три раза превышающую массу американской БР Баллистическая ракета Поларис А1 и дальность пуска 2400 км. Работы по комплексу Д-7 были доведены до стадии бросковых испытаний, однако в 1962 г., когда заказчик выдвинул требование резкого увеличения боекомплекта ракетоносцев (и, следовательно, уменьшения габаритов ракет), интерес к программе стал постепенно угасать, а в 1964 г. она была вовсе прекращена из-за невозможности разработчиков уложиться в рамки новых требований. В то же время в КБ «Арсенал» продолжались работы над стратегическими ракетами наземного базирования, завершившиеся принятием на вооружение в 1972 г. БР Баллистическая ракета средней дальности 8К98П. Накопленный опыт по созданию двигателей на смесевом топливе позволил «Арсеналу» выйти с предложением о разработке для модернизированной ПЛАРБ Атомная подводная лодка с баллистическими ракетами проекта 667A Навага твердотопливной ракеты, которую можно было бы разместить в шахтах, созданных для БР Баллистическая ракета Р-27. При этом дальность пуска новой ракеты должна была в 1,5 раза превосходить дальность своей предшественницы, приближаясь к возможностям новейшей американской ракеты Посейдон С3.
Внешне модернизированный корабль отличался от ПЛАРБ Атомная подводная лодка с баллистическими ракетами проекта 667A Навага кормовой надстройкой, имеющей несколько меньшую длину и большую высоту. Немного возросло и полное водоизмещение подводной лодки. Старт ракеты производился посредством порохового аккумулятора с глубины до 50 м, без предварительного заполнения шахты водой (что повышало скрытность боевого применения, так как поступление воды в кольцевой зазор демаскировало корабль во время предстартовой подготовки). Пуск был возможен при волнении моря до 8 баллов. Весь боекомплект выстреливался в течение одной минуты единым залпом. Время предстартовой подготовки составляло 3,5 мин.
Для переоборудования по проекту "667АМ" была выделена подводная лодка K-140 — второй корабль проекта 667A Навага. Работы по модернизации атомохода начались на судоремонтном заводе «Звездочка» в Северодвинске в 1973 г. Первый пуск Р-31 с борта К-140 состоялся 26 декабря 1976 г. из акватории Белого моря. Во время испытаний лодки были проведены две стрельбы на максимальную дальность (более 4000 км). Для этого лодке пришлось идти к северной оконечности Новой Земли и оттуда с параллели 77° северный широты стрелять по боевому полю «Кура» на Камчатке.