С 19 по 23 января Су-33 выполнили 67 полетов. Вертолеты Ка-27 отрабатывали поиск подводных лодок. 24 января корабль принимал запасы, стоя на якоре, а 26 января взял курс к берегам Сирии. На переходе два Су-33 осуществили перехват пары истребителей F-16 ВВС Израиля.
С 28 января по 2 февраля состоялся деловой заход в сирийский порт Тартус, а 3 февраля «Адмирал Кузнецов» вновь вышел в море. К тому времени ситуация с котлами на авианосце еще больше осложнилась. В Средиземное море на разведывательном судне «Кавказ» срочно вышел начальник Главного штаба ВМФ вице-адмирал В.Е. Селиванов. 4 февраля у острова Крит он сменил адмирала И.В. Касатонова и поднял на ТАВКР свой фла г. Было проведено внеплановое учение по буксировке «Адмирала Кузнецова» спасательным буксиром «Шахтер».
8—9 февраля корабли АМГ попали в пыльную бурю, а после пополнения запасов на границе территориальных вод Ливии и Египта взяли курс на Мальту. Визит «Адмирала Кузнецова» в Ла-Валлетту продлился с 17 по 18 февраля, после чего из-за проблем с котлами и надвигавшегося шторма был прерван, и корабль снова вышел в открытое море.
2 марта впервые на Средиземном море прошло летно-тактическое учение в ближней и дальней зонах ПВО АМГ с отработкой истребителями задач по перехвату самолетов и атакующих крылатых ракет. Отсутствие на борту самолетов и вертолетов радиолокационного дозора компенсировалось организацией полуавтономного патрулирования Су-33 по данным выдвинутого на угрожаемое направление корабля радиолокационного дозора – эсминец «Бесстрашный».
6 марта корабли соединения прошли Гибралтар и вышли в Атлантику. В британской зоне ответственности ТАВКР был взят на сопровождение фрегатом «Шеффилд», вертолет которого с разрешения российского адмирала садился и взлетал с палубы «Адмирала Кузнецова».
На завершающем этапе похода, по прохождении Фарерско-Исландского рубежа, наши корабли приняли участие в командно-штабных учениях Северного флота. 20 марта палубные Су-33 успешно отражали ракетную атаку условного противника (четыре Ту-22М3), перехватив с участием корабля радиолокационного дозора (эсминец «Бесстрашный») бомбардировщики на 450-километровом удалении от центра охраняемого ордера. В ходе этих учений на одном из Су-33 (М.Ф. Савицкий) произошел частичный отказ одного двигателя. В условиях отсутствия запасных аэродромов пилот сумел с первого захода посадить аварийную машину на палубу «Адмирала Кузнецова» (позже за это он был удостоен звания Героя России). 22 марта 1996 г. ТАВКР ошвартовался у своего причала в Видяеве.
Всего за время похода кораблем было пройдено более 14 156 миль, выполнено 524 полета самолетами и 996 вертолетами, фактически перехвачено 12 воздушных целей, обнаружены две иностранные подводные лодки, отработаны учебно-боевые задачи по двум своим подводным лодкам, успешно проведены ракетно-артиллерийские стрельбы, в том числе главным ударным комплексом. Осуществлявшая задачу дальнего противолодочного обеспечения крейсера, атомная подводная лодка «Волк» (капитан 2 ранга С. Справцев) выполнила скрытное длительное слежение за несколькими натовскими субмаринами, включая одну американскую атомную подводную лодку типа «Лос-Анджелес».