На стапеле Завода № 199 в Комсомольске-на-Амуре была заложена головная атомная подводная лодка с крылатыми ракетами К-45 проекта «659». В сентябре 1956 г., одновременно с началом разработки ПЛАРБ проекта «658», ЦКБ-18 приступило к разработке технического проекта атомных подводных лодок, вооруженных шестью крылатыми ракетами П-5, — проекту «659». Разработка обоих проектов велась параллельно в одни и те же сроки.
23 октября 1956 г., когда значительная часть проекта уже была разработана, Главнокомандующий ВМФ С.Г. Горшков утвердил тактико-техническое задание на разработку атомной подводной лодки с реактивным вооружением — комплексом П-5, предназначавшейся для нанесения ударов самолетами-снарядами по военно-морским базам, портам, промышленным и административным центрам, расположенным на побережье и в глубине территории в пределах досягаемости полета самолетов-снарядов. Всего по проекту «659» было построено пять подводных лодок.