Единственной строевой авиачастью, вооруженной Су-33, стал 279-й корабельный истребительный авиаполк (КИАП). Он входил в 57-ю Смоленскую Краснознаменную смешанную корабельную авиадивизию (СКАД), в составе которой находился также 830-й корабельный противолодочный вертолетный полк (КПЛВП), оснащенный Ка-27, Ка-27ПС и Ка-29. Именно этому соединению предстояло нести службу на борту «Кузнецова» при выходе его в море.
279-й полк начал свою историю в 1973 г. Двадцать лет он назывался корабельным штурмовым и был вооружен сначала СВВП Як-38, а после прекращения их эксплуатации сухопутными Су-25. В 1992 г. начался истребительный этап в биографии этой части. Летом летчик- испытатель ОКБ Сухого С.Н.Мельников на «фирменном» Су-27УБ начал вывозить пилотов полка, которые приступили к освоению нового для себя типа самолета. Для тренировок использовались и учебно-тренировочные Су-25УТГ, поступившие с авиазавода в Улан- Удэ. В дальнейшем из 7 таких самолетов сформировали 3-ю эскадрилью 279-го КИАП. Весной 1993 г. прибыли в Североморск первые четыре серийные Су-27К К тому времени полк получил драгоценное пополнение. В него влились около сотни офицеров 100-го ИИИАП, в т.ч. 16 летчиков, которые во главе с п-ком Апакидзе покинули берега теплого Крыма и прибыли на Север, отдав предпочтение службе ВМФ России перед неясными перспективами пребывания в Вооруженных Силах Украины.
В 1994 г. была достигнута договоренность об аренде Россией комплекса «Нитка», и в июле в Саки прибыла лидерная группа из 10 летчиков 279-го КИАП во главе с его командиром п-ком И.И.Бохонко и начальником воздушно- огневой и тактической подготовки 57-й СКАД п-ком ТААпакидзе. Месяц тренировок в Крыму позволил подготовиться к полетам с корабля. В августе «Адмирал Кузнецов» вышел в Баренцево море, и 31 числа командир эскадрильи 279- го КИАП подп-к И.С.Кожин впервые в истории этой части посадил Су-27К на палубу. В тот же день посадки совершили подп-ки В.В.Дубовой и К.Б.Кочкарев. 2 сентября к ним присоединились п-к И.И.Бохонко, подп-к Г.Б.Рыжов и к-н Е.В.Кузнецов, 9 сентября – м-р П.З.Подгузов, а 15 октября – к-н А.А.Абрамов. Во время этого выхода в море совершили полеты с корабля представители командования 57-й дивизии п- ки Т.А.Апакидзе и Я.Г.Чибир, а также летчики- испытатели ГЛИЦ подп-ки А.Иванов, В.Петруша, В.Крицкий и С.Богдан. Во второй кабине Су-25УТГ посадки на палубу крейсера выполнили также командующий авиацией ВМФ генерал-лейтенант В.Дейнека, его первый заместитель генерал-лейтенант Н.Рогов, командующий Северным флотом адмирал О.Ерофеев, командующий авиацией Северного флота генерал-майор Н.Мордовалов, командир ТАВКР капитан 1-го ранга И.Санько, начальник ГЛИЦ генерал-майор Ю.Клишин.
Подготовка лидерной группы корабельных летчиков-истребителей ВВС Северного флота завершилась проведением зачетного учения. Сначала с корабля взлетела пара самолетов, которые пилотировали летчики-испытатели Пугачев и Мельников. Они имитировали действия противника, наносящего удар по корабельной группировке с удаления 800 км от местоположения крейсера. Прикрытие корабля и перехват воздушных целей выполняли две пары североморцев: Апакидзе-Дубовой и Кожин-Кочкарев. По результатам первого этапа подготовки авиагруппы и авиационного комплекса ТАВКР «Адмирал Кузнецов» к несению боевой службы наиболее отличившиеся летчики были представлены к государственным наградам. При этом ставший командиром 57-й СКАД и получивший звание генерал-майора Т.А.Апакидзе, а также командир 279-го полка п-к И.И.Бохонко были удостоены звания Героя России.
К концу октября 1995 г. к полетам с корабля было подготовлено уже 15 летчиков 279-го КИАП. На аэродром Североморск-3 с завода- изготовителя прибыли 24 серийных Су-27К, которыми были полностью укомплектованы две авиационные эскадрильи, причем первая была введена в состав сил постоянной боевой готовности Краснознаменного Северного флота. Самолеты 1-й эскадрильи (бортовые номера с 60 по 73 и 76) получили на килях эмблему в виде орла. Во 2-й АЭ находились самолеты с бортовыми номерами от 77 по 88, на килях некоторых из них были изображены головы тигров.
ПоходВ конце декабря 1995 г. «Адмирал Кузнецов» вышел в свой первый длительный поход. В ходе трехмесячного плавания кораблю, которым командовал капитан 1-го ранга А.В.Челпанов, предстояло преодолеть более 10 000 миль, побывать в водах двух океанов, Баренцева, Норвежского и Средиземного морей. Кроме ТАВКР, в авианосно-многоцелевую группу (АМГ) вошли: эсминец «Бесстрашный», танкер «Днестр» и буксир СБ-406 Северного флота, а в Средиземном море к ним присоединились сторожевой корабль (СКР) «Пылкий» и танкер «Олекма» Балтфлота. Возглавлял АМГ контр-адмирал В.Г.Доброскоченко. Старшим военно- морским начальником во время похода был заместитель Главкома ВМФ России адмирал И.В.Касатонов, которого в Средиземноморье при встрече с большим разведывательным кораблем «Кавказ» сменил начальник Главного штаба ВМФ РФ адмирал В.Е.Селиванов. Старшим авиационным начальником на поход был назначен первый заместитель командующего ВВС СФ генерал-майор В.Новичков. Непосредственное руководство действиями авиагруппы осуществлял генерал-майор Т.А.Апакидзе.