Необходимость создания противокорабельной ракеты подводного старта, по дальности не уступающей ракете комплекса «Базальт», определилась еще в середине 1960-х гг. После отстранения Н.С. Хрущева с высших партийно-государственных постов в ходе ревизии тематики работ В.Н. Челомею была поставлена задача обеспечения подводного старта для ракет комплекса П-500 «Базальт», уже находившихся на достаточно продвинутой стадии разработки. Однако этот комплекс предназначался для оснащения надводных кораблей, а также для перевооружения подводных лодок семейства пр. 675, пусковые установки которых не допускали подъема контейнеров для пуска ракет при движении атомохода под водой. Переоборудование лодок под пусковые установки, зафиксированные в наклонном положении для подводного пуска ракет (например, по типу реализованных для комплекса «Аметист»), потребовало бы радикального изменения общей архитектуры корабля, а стоимость и длительность модернизационного ремонта сравнялась бы с новым строительством. Да и компоновка ракеты «Базальт» с подфюзеляжным расположением воздухозаборника не отвечала условиям подводного старта.
Используя эти обстоятельства, В.Н. Челомей сумел «разрулить» ситуацию. Работы по «Базальту» продолжились применительно к ракете надводного старта, а новый комплекс П-500П с ракетой подводного старта на дальность 400—600 км со скоростью полета 3200—3600 км/ч предусматривалось создать в более поздние сроки для вооружения перспективных подводных лодок пр. 688.
Первоначально предусматривалось вписать новую ракету в габариты пусковой установки комплекса «Малахит», что открывало перспективу перевооружения этим комплексом лодок пр. 670М либо оснащения им очередной модификации лодок сормовской постройки. Но этим планам помешали, с одной стороны, свойство практически всех летательных аппаратов «грузнеть» в процессе разработки, а с другой — выявившаяся неперспективность лодок семейства пр. 670 как носителей противоавианосного ракетного комплекса. С конца 1960-х гг. в США началась разработка нового авиационно-ракетного комплекса на базе истребителя F-14 и ракеты «Феникс». Истребитель F-14 оснащался РЛС, способной обеспечить одновременный обстрел до шести воздушных целей (в том числе и в нижней полусфере, на фоне водной поверхности), а дальность ракет класса «воздух— воздух» составила более 140 км.
Как показали расчеты боевой эффективности, в этих условиях поражение авианосца могло быть достигнуто только массированным залпом не менее чем двух десятков крылатых ракет с высокими летно-тактическими характеристиками, при условии применения на этих ракетах наиболее современных достижений в области радиоэлектронной борьбы. Напротив, бесполезность использования малочисленных противокорабельных ракет наглядно подтверждалась практикой учебных зенитных стрельб наших кораблей. Используя далеко не самые совершенные зенитные ракетные комплексы, они уверенно сбивали переделанные в мишени собственные противокорабельные ракеты. Таким образом, разработка нового комплекса должна была вестись для вооружения подводных атомоходов уже следующего, третьего, поколения с большим боекомплектом ракет, а задача обеспечения высокой боевой эффективности получила явный приоритет по сравнению с унификацией по пусковой установке с ранее разработанной ракетой.
Решением ВПК от 8 апреля 1966 г. ОКБ-52 предлагалось в I кв. следующего года представить аванпроект противокорабельной крылатой ракеты «Гранит» с дальностью полета 700—800 км при скорости полета 3500—4000 км/ч на высоте 20—24 км. При пуске по маловысотной траектории допускалось снижение максимальной дальности до 200 км. Как уже упоминалось, ракета должна была размещаться в пусковых контейнерах комплекса «Малахит». Работы по новой теме в реутовской организации возглавил В.И. Патрушев, затем — В.А. Вишняков.
При выполнении аванпроекта выявилась несовместимость заданных летно-технических характеристик с установленными габаритными ограничениями. Проведенные проектные проработки показали, что длина ракеты составит 13 м, что в 1,8 раз превышало соответствующий показатель «Малахита». Кроме того, обеспечение заданных скоростных и высотных характеристик требовало реализации ряда принципиально новых технических решений. В частности, достижение заданных высоких летно-технических характеристик исключало использование твердотопливного двигателя в качестве маршевого.
