Партийно-правительственное постановление о создании атомной ракетной подводной лодки проекта 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 ракет (два ряда по восемь шахт).