Опыт, накопленный в ходе проектирования и постройки первых отечественных атомных торпедных подводных лодок, а также дизель-электрических ракетоносцев проектов В611 и 629, позволил в середине 1950-х годов приступить к созданию первого советского подводного атомохода, оснащенного баллистическими ракетами. Корабль предназначался для нанесения ракетно-ядерных ударов по военно- морским базам, портам, промышленным и административным центрам, расположенным на побережье и в глубине территории противника.
Для сокращения сроков реализации программы, а также снижения технического риска при создании принципиально нового класса боевых кораблей, было решено разработать первую советскую ПЛАРБ на основе конструкционных решений, реализованных на торпедной атомной подводной лодке проекта 627. Собственно, новую субмарину можно было рассматривать как модификацию лодки «Ленинский комсомол» с врезанным в корпус дополнительным ракетным отсеком.
Партийно-правительственное постановление о создании атомной ракетной подводной лодки проекта 658 вышло 26 августа 1956 г. Проектирование корабля было поручено ЦКБ- 18 (впоследствии – ЦКБ «Рубин»), Разработка конструкторской документации началась в сентябре 1956 г., работы велись под руководством главного конструктора С.Н.Ковалева. Заместителем главного конструктора с самого начала работ над проектом был И.Д.Спасский.
Техническое проектирование было завершено в первом квартале 1957 года (эскизный проект подводной лодки не разрабатывался из-за предельно сжатых сроков, диктуемых реалиями «гонки вооружений»).
В соответствии с первоначальными планами корабль предполагалось оснастить оружием, создание которого уже близилось к завершению – ракетным комплексом Д-2 с жидкостными ракетами Р-13, имеющими надводный старт (испытания этого комплекса, изначально разрабатывавшегося для вооружения дизель-электрических подводных лодок 629-го проекта, начались в декабре 1958 г.). Однако в 1958 году было решено приступить к разработке проекта 658М, предусматривающего переоснащение лодки более перспективными ракетами с подводным стартом. Правительственное постановление о создании нового ракетного комплекса Д-4 вышло 20 марта 1958 г. Комплекс предполагалось установить на атомоходах в процессе капитального ремонта и модернизации.
Работы по созданию первой советской ПЛАРБ развернулись практически одновременно с аналогичными работами в США, где в 1956 году началась реализация программы «Поларис». Однако если в Советском Союзе подводную лодку проекта 658 рассматривали как своего рода синтез уже существующих технологий, то американский флот создавал принципиально новую систему оружия, в основе которой лежала не имеющая аналогов малогабаритная твердотопливная баллистическая ракета с подводным стартом, обладающая значительно большими возможностями, чем ее советский аналог. В то же время первый носитель «Поларисов» – ПЛАРБ «Джордж Вашингтон», как и лодка пр.658, разрабатывался на основе уже существующего проекта-торпедного атомохода типа «Скипджек». Более того, при постройке первой серии американских ПЛАРБ были использованы уже готовые корпусные конструкции АПЛ, в результате чего головной американский подводный ракетоносец был сдан флоту 30 декабря 1959 г., на год раньше, чем его советский аналог. Малые габариты «Поларисов» (длина 8,68 м, диаметр 1,37 м), а также более простое и компактное пусковое устройство позволили разместить на «Джордже Вашингтоне» 16 ракет (два ряда по восемь шахт).
«Генетическая связь» проекта 658 с проектом 627, обусловившая относительно малую ширину прочного корпуса корабля, а также солидные габариты отечественных баллистических ракет, громоздкие и сложные стартовые устройства (разрабатывавшиеся по нормам проектирования артиллерийских установок для тяжелых надводных кораблей), допускали размещение ракетных шахт на лодке лишь в один ряд. Три ракеты расположили в ограждении рубки, которая в результате этого получила необычайно крупные, весьма далекие от оптимальных (с точки зрения гидродинамики) габариты.
По сравнению с торпедной лодкой пр.627 в конструкцию ракетного атомохода был внесен ряд существенных изменений. В частности, для управления на больших скоростях были применены малые горизонтальные кормовые рули. Лодка получила малошумную и более живучую электрогидравлическую систему управления рулями. Предусматривалось продувание главного балласта воздухом низкого давления. Внедрялась автономная система пожаротушения в реакторном отсеке. Из-за требований обеспечения высокой мореходности в надводном положении, во время предстартовой подготовки и пуска ракет, пришлось отказаться от «торпедообразной» формы носовой оконечности лодки и вернуться к традиционным «корабельным» обводам.