17 августа 1956 года вышло Постановление СМ CCCH № 1149-592 о начале разработки противокорабельных крылатых ракет П-6 и П-35. Обе ракеты проектировались в ОКБ-52 и мало отличались друг от друга. П-6 предназначалась для подводных лодок, а П-35 — для надводных кораблей.
Пусковые установки для П-35 СМ-70, СМ-82 и СМЭ-142 проектировались ЦКБ-34 совместно с ЦНИИ-173 (приводы наведения), а изготавливались на заводе «Большевик». Задание на разработку штатной пусковой установки СМ-70 для крейсеров проекта 58 было выдано ЦКБ-34 в декабре 1956 года. Четырехконтейнерная пусковая установка СМ-82 предназначалась для наземных испытаний комплекса, а одноконтейнерная пусковая установка СМЭ-142 — для испытаний на опытном судне ОС-15 (переоборудованный в 1959 году сухогруз «Илеть»).
Первый пуск ракеты П-35 состоялся 21 октября 1959 года. Параллельно с испытаниями П-35 шла достройка крейсеров проекта 58. Первый корабль проекта 58 «Грозный» был заложен 23 февраля 1960 года и спущен 26 марта 1961 года, в том же году на нем были смонтированы первые 2 счетверенные наводящиеся пусковые установки СМ-70. Всего на заводе им. Жданова в Ленинграде были построены четыре крейсера проекта 58 («Грозный», «Адмирал Фокин», «Адмирал Головко» и «Варяг»). В 1964-1968 годах на том же заводе были заложены четыре больших противолодочных корабля проекта 1134 («Адмирал Зозуля», «Владивосток», «Вице-адмирал Дрозд» и «Севастополь»). Корабли проекта 1134 вооружили ракетами П-35, установленными в двух спаренных пусковых установках КТ-35. Поворотного механизма пусковые установки не имели, и наведение установок производилось поворотом корпуса корабля. По проекту предусматривалось размещение четырех запасных ракет в погребах на верхней палубе. Однако в ходе строительства кораблей от перезарядки ракет отказались.
На базе ракеты П-35 в 1966 году был создан береговой комплекс "Редут".