Старт ракеты П-35 берегового стационарного комплекса «Утес».

Автономные испытания наземного оборудования начались в середине 1968 г. и продолжались более двух лет. 28 мая 1971 г. был проведен первый пуск П-35 на дальность около 200 км.

Работы в первом дивизионе завершились 25 февраля 1972 г., а 17 апреля следующего года успешно прошла стрельба по цели пр. 1784 на дальность 217 км.

28 апреля 1973 г. оба дивизиона полка поступили на вооружение. В 1978— 1983 гг. было выполнено 33 пуска, из них 30 — успешно.

Каждый дивизион помимо двух стартовых батарей включал еще три: техническую, телеуправления ракетами и электротехническую, а также хозяйственную роту. В полковую структуру помимо штаба и двух ракетных дивизионов входили радиотехническая батарея и автотехнический взвод.

Перевооружение дивизионов 616-го отдельного берегового ракетного полка Северного флота на острове Кильдин завершилось в 1976 и в 1983 г.

В 1974 г. началась модернизация береговых ракетных комплексов под ракету «Прогресс». В 1976 г. полк на мысе Айя выполнил шесть испытательных пусков. В 1996 г. славяне по-братски поделили полк: один из дивизионов был передан Украине и, по сообщениям печати, в настоящее время расформирован. Второй остался в составе российского Черноморского флота.

На кадрах из отечественного художественного фильма «Одиночное плавание» показана предстартовая подготовка ракеты П-35 комплекса «Утес», изображающей американскую крылатую ракету со специальной боевой частью.