Разработка крылатой противокорабельной ракеты П-500 "Базальт" была начата ОКБ Опытно-конструкторское бюро-52 в 1963 году. "Базальт" предназначался для борьбы с самыми мощными корабельными группировками, включая и авианосные. Им предусматривалось вооружить как подводные лодки, так и надводные корабли. Ракета «Базальт» предназначалась для замены ракеты П-6 и имела приблизительно те же весогабаритные характеристики.
В 1975 году ракета "Базальт" принимается на вооружение атомных подводных лодок проекта 675, которые были ранее вооружены комплексом П-6. А в 1977 году "Базальт" принимается на вооружение авианесущих крейсеров типа Krechyet. Первые три корабля этого проекта имели по четыре спаренные пусковые установки с восемью ракетами П-500 в контейнерах и восемью запасными в погребе, а четвертый крейсер Gorshkov имел шесть спаренных установок. На крейсерах типа Atlant, вошедших в строй в 1982 году, ракеты П-500 располагались в шестнадцати ненаводящихся контейнерах, без перезарядки.
По аэродинамической и конструктивно-компоновочной схеме П-500 была подобна П-6, но обладала большей скоростью полета, увеличенной дальностью стрельбы и более мощной фугасно-кумулятивной боевой частью, спроектированной в ГСКБ-47. Могла применяться и ядерная боевая часть. Ракета "Базальт" была первой крылатой ракетой морского базирования с высокой сверхзвуковой (до 2М) скоростью полета. Это существенным образом сказалось на конструкции. Был разработан подфюзеляжный секторный воздухозаборник с двухскачковым центральным телом. В конструкции ракеты использовались титановые сплавы, обладающие необходимыми прочностными характеристиками при повышенной температуре. Исследованию конструкции при одновременном воздействии силовых факторов нагружения и температурного нагрева было уделено самое пристальное внимание.
На П-500 был сохранен принцип телеуправления, но устанавливалась более современная система управления повышенной помехозащищенности, позволяющая осуществлять целераспределение ракет в залпе (до 8 ракет) и избирательное поражение головных целей из состава атакуемого корабельного соединения. Впервые на ПКР Противокорабельные ракеты была использована бортовая станция радиоэлектронного противодействия (активных помех), которая воздействовала на ГСН Головка самонаведения ЗУР Зенитная управляемая ракета противника и обеспечивала неуязвимость КР Крылатая ракета в зоне ПВО Противо-воздушная оборона атакуемого корабля.
Специально для П-500 был создан маршевый турбореактивный двигатель повышенной тяги и экономичности КР Крылатая ракета-17-300, разработанный в ОКБ Опытно-конструкторское бюро-300 ГКАТ.
"Базальт" стал последней ракетой, предназначенной для размещения на подводных лодках и запускавшейся в надводном положении. Как и П-6, ракета "Базальт" имела профиль полета "большая высота — малая высота", но в отличие от П-6 длина конечного участка ("малая высота") была увеличена, а высота полета на этом участке уменьшена.
Обнаружение целей и наведение комплекса "Базальт", как и последующих комплексов "Вулкан" и SS-N-19 Shipwreck, осуществлялось с помощью системы морской космической разведки и целеуказания (МКРЦ). Полномасштабная разработка системы МКРЦ была начата в 1962 году.
В ее состав вошли:
радиолокационный разведывательный комплекс для обнаружения надводных морских целей из космоса;
радиотехнический разведывательный комплекс для обнаружения из космоса излучений корабельных радиотехнических средств;
ядерная энергетическая установка, обеспечивающая электропитанием космические аппараты.
Работы по созданию системы МКРЦ "Легенда" и передача ее на вооружение МО СССР с космическими аппаратами радиолокационной разведки были завершены в 1975 году, а с космическими аппаратами радиотехнической разведки — в 1978 году.