Однако эффективность противокорабельного ракетного комплекса большой дальности в значительной степени определялась возможностями средств разведки и целеуказания. Система «Успех», основу которой составлял самолет Ту-95, уже не обладала необходимой боевой устойчивостью.
В начале 60-х годов перед отраслевой наукой и промышленностью была поставлена задача создания первой в мире космической всепогодной системы наблюдения за надводными целями на всей акватории мирового океана и выдачи целеуказания с передачей данных непосредственно на носители оружия или наземные (корабельные) командные пункты. Первое правительственное постановление о развертывании опытно-конструкторских работ по созданию системы морской космической разведки и целеуказания (МКРЦ) вышло в марте 1961 г. К этой широкомасштабной работе были привлечены крупнейшие научные центры и конструкторские коллективы страны, в частности, Физико-энергетический институт и Институт атомной энергии им. И.В. Курчатова. Теоретические основы построения системы, параметры орбит и взаимное расположение космических аппаратов были выработаны при непосредственном участии академика М.В. Келдыша.
Головной организацией, отвечающей за создание МКРЦ, было первоначально определено ОКБ-52 (позже – НПО «Машиностроение»), возглавляемое генеральным конструктором В.Н. Челомеем. За разработку уникальной (до сих пор не имеющей мировых аналогов) ядерной бортовой энергетической установки для ИСЗ, входящих в состав системы, отвечал коллектив ОКБ-670 (НПО «Красная Звезда») Минсредмаша.
Однако НПО «Машиностроение» не обладало необходимыми производственными мощностями, обеспечивающими выпуск серии космических аппаратов для ВМФ. В результате в мае 1969 г. к программе было решено подключить ленинградские КБ и завод «Арсенал» им. М.В. Фрунзе, ставшие головными в реализации программы «морских» спутников.
Система МКРЦ «Легенда» включала два типа космических аппаратов: спутник с бортовой радиолокационной станцией и ядерной энергетической установкой, а также спутник с космической станцией радиотехнической разведки, оснащенный солнечной энергетической установкой.
Уже в начале 1970 года завод «Арсенал» приступил к производству опытных образцов космических аппаратов. Летно-конструкторские испытания КА радиолокационной разведки начались в 1973 году, а спутника радиотехнической разведки – годом позже. КА радиолокационной разведки был принят на вооружение в 1975 году, а комплекс в полном составе (с КА радиотехнической разведки) в 1978 году.
В 1979-1989 гг. был выполнен ряд этапов модернизации космических аппаратов морской разведки, обеспечивших существенное повышение всех параметров космических комплексов (улучшение характеристик обнаружения и распознавания, увеличение полосы одновременного обзора и т. п.). Ресурс полетного функционирования КА был повышен в 5-10 раз, что, в свою очередь, позволило существенно уменьшить годовой наряд космических аппаратов до уровня, сбалансированного с производственными возможностями предприятий-изготовителей.