Преследуемые роем катеров с фотографами, оснащёнными первоклассной аппаратурой, корабли проследовали в Мраморное, а затем в Эгейское и Средиземное море.
В первом походе принимал участие заместитель командующего авиацией ЧФ. Группой из 14 вертолётов командовал заместитель командира 872-го оплвп подполковник Г.Н. Мдивани.
После проведения нескольких учений в Средиземном море между о. Крит и северным побережьем Африки началась поисковая противолодочная операция под кодовым обозначением "Удав". В ней принимали участие надводные корабли, ПЛ, самолёты Бе-12, вертолёты Ка-25ПЛ и Ка-25Ц.
Вопреки ожиданиям, первый контакт с иностранной ПЛ установил ПКР с помощью гидроакустической станции "Орион". Экипажи вертолётов контакт подтвердили, через 19 мин потеряли, вновь восстановили на перехватывающем барьере из буёв и следили за лодкой 47 мин. Такими скромными оказались итоги почти трехсуточных усилий значительного количества привлечённых сил. Полёты корабельных вертолётов существенно затрудняли американские вертолёты и самолёты, действовавшие нагло, беспардонно, не раз создававшие аварийные ситуации.
В начале ноября 1968 г. ПКР "Москва" с сопровождающими его кораблями возвратился в Севастополь.
По итогам первого выхода ПКР на боевую службу в 872-м оплвп провели конференцию. На основании анализа пришли к заключению, что количество вертолётов на корабле следует увеличить до 18 или даже 24, что впоследствии и сделали, но это привело к ухудшению условий размещения личного состава. Много неприятностей доставил короткий кабель-трос, который не обеспечивал заглубление антенны ВГС-2 под слой температурного скачка; пришлось также заменить 21 кабель-трос из-за затекания воды.
Крейсер "Москва" в боевом походе в сопровождении американского крейсера
Ка-25 вместе с основным вертолетом ПЛО стран НАТО SH-3H "Си Кинг'
Довольно часто экипажи прекращали задание из-за сбоев автоматики топливной системы двигателей и отказов автопилота. Отказывали даже электрические лебёдки ОГАС.
Полёты на малых высотах, а особенно висение, сопровождались усиленным брызгообразованием, интенсивным отложением солей на элементах конструкции вертолёта и нарушением электрических соединений. Инженерно-технический состав пытался бороться с отложением солей, обтирая вертолёт после полёта ветошью. Как и следовало ожидать, это не привело к должному эффекту. В первом походе на боевую службу проточную часть двигателей после полёта не обрабатывали, и после возвращения в Севастополь несколько двигателей пришлось перебирать.
Не ожидая, пока будут проведены НИР и ОКР, составлены пухлые отчёты, разработан макет и т.п., инженеры и техники своими силами соорудили агрегат для промывки двигателей пресной водой. Это была нехитрая конструкция из подвесного топливного бака с самолёта МиГ-15 ёмкостью 250 л, установленного на колёса и снабжённого центробежным насосом. Перед применением бак заполнялся горячей водой, которая после включения насоса подавалась к двум коллекторам с форсунками, смонтированными на штангах. Техник вертолёта подводил их к работающему двигателю и включал подачу воды. Таким методом воздушный тракт двигателей очищался от солей.
Противолодочный крейсер "Москва" в 1969 г. ещё дважды выходил на боевую службу в Средиземное море и во взаимодействии с 5-й эскадрой кораблей ВМФ участвовал в учениях и поисковых операциях. Однако получаемые результаты далеко не всегда оказывались адекватны затраченным усилиям, а некоторые из них наводили на размышления.
Так, в третьем походе было получено девять обнаружений ПЛ, и все их без достаточных оснований классифицировали как принадлежащие ПЛАРБ. Настораживал и тот факт, что в восьми случаях из девяти средством первичного обнаружения являлись не вертолетные, а корабельные ГАС. Учитывая преимущества подводных лодок в дальности обнаружения шумов кораблей (порядка 120-180 км в зависимости от скорости и состава группы) становилось ясно, что противолодочные крейсера вряд ли были способны решить подобную задачу.
Кроме того, за нашими кораблями велось систематическое наблюдение патрульными самолётами "Орион". Это наводило на мысль, что или контакты с ПЛ ложные, или, что совершенно маловероятно, лодки специально "подставлялись" для изучения тактики действий и возможностей наших корабельных и авиационных противолодочных средств. Проделать «подставу» с вертолётами было сложнее, учитывая непредсказуемость траектории их маневрирования и значительные скорости полёта.
Первый опыт тщательно анализировался, делались соответствующие выводы, разрабатывались приёмы действий, основанные на внезапности, отчасти даже хитрости.
В середине октября 1968 г. на другом флоте экипажи вертолётов Ка-25ПЛ 710-го оплвп на крейсере "Адмирал Сенявин" и БПК "Маршал Ворошилов" и судах: "Чажма " и "Чумикан" отправились в трёхмесячный поход за экватор. На судах базировались вертолёты Ка-25ИВ, предназначенные для контроля за приводнением объектов, возвращающихся из космоса.
Подводя некоторый итог развития морской авиации в 60-е годы, необходимо отметить, что именно в это время фактически были заложены основы новой морской авиации, определены направления развития её техники и оружия на ближайшую перспективу: расширение рубежа досягаемости, увеличение дальности пуска ракет, массовое освоение заправки в полёте, выполнение полётов с посадками на аэродромах дружественных стран, расширение возможностей вертолетного парка.