23 декабря 1995 г. «Адмирал Кузнецов» (бортовой № 063) впервые вышел на БС в Средиземное море. В возглавляемую им АМГ под командованием контр-адмирала В. Г. Доброскоченко (старший на борту – первый заместитель главкома ВМФ РФ адмирал И. В. Касатонов) входили ЭМ «Бесстрашный», многоцелевая АПЛ «Волк», танкер «Днестр» и буксир СБ-406 Северного флота, СКР «Пылкий» и танкер «Олекма» Балтийского флота, а также буксир «Шахтер» и танкер «Иван Бубнов» из состава Черноморского флота. Авиагруппа ТАВКР включала 13 самолетов Су-33, 2 – Су-25УТГ и 11 вертолетов Ка-27, Ка-27ПС и Ка-29 из состава 57-й СКАД (командир – генерал-майор Т. А. Апакидзе).

Поход начался в сложных метеоусловиях. Уже на выходе из Кольского залива корабли попали в семибалльный шторм, а у мыса Нордкап вышли из строя два главных котла с потерей мощности ГЭУ. Первые восемь полетов состоялись только 29 декабря в районе западного побережья Великобритании. Палубные Су-33 выполнили три учебных перехвата британских и голландских патрульных самолетов «Орион» и «Нимрод». Из-за проблем с котлами «Кузнецов» следовал малым ходом. Тем не менее 4 и 5 января полеты авиации были возобновлены. 7 января «Кузнецов» стал на якорь у берегов Туниса, и до 17-го числа на нем устраняли неисправности. Там же впервые состоялись обмены визитами российских и американских моряков (авианосец «America»), при этом на палубу «Кузнецова» совершили посадку два вертолета SH-60 «Sea Hawk». Некоторые российские летчики в ходе проведения совместных учений летали в качестве вторых пилотов на американских палубных самолетах и вертолетах (в том числе В. Г. Пугачев – на истребителе F-14 «Tomcat», Т. А. Апакидзе – на противолодочном S-3A «Viking). В свою очередь, российские вертолеты более 30 раз садились на ВПП кораблей 6-го флота ВМС США, а командующий 6-м флотом адмирал Пиллинг с группой офицеров подробно ознакомился на борту «Кузнецова» с палубным истребителем Су-33.

С 19 по 23 января Су-33 выполнили 67 полетов. Вертолеты Ка-27 отрабатывали поиск ПЛ. 24 января корабль принимал запасы, стоя на якоре, а 26 января взял курс к берегам Сирии. На переходе два Су-33 осуществили перехват пары истребителей F-16 ВВС Израиля.

С 28 января по 2 февраля состоялся деловой заход в сирийский порт Тартус, а 3 февраля «Кузнецов» вновь вышел в море. К тому времени ситуация с котлами на авианосце еще больше осложнилась. В Средиземное море срочно вышел Начальник Главного штаба ВМФ вице-адмирал В. Е. Селиванов. 4 февраля у о. Крит он сменил адмирала И. В. Касатонова и поднял на ТАВКР свой флаг. Было проведено внеплановое учение по буксировке «Адмирала Кузнецова» спасательным буксиром «Шахтер».

Поход ТАВКР «Адмирал Кузнецов» в Средиземное море был спланирован по решению администрации Кремля для демонстрации военной мощи государства в ознаменование трехсотлетия Российского флота. Был намечен визит крейсера в столицу Мальты Ла-Валетту в период с 17 по 18 февраля. Но из-за проблем с котлами и надвигавшегося шторма визит был прерван.

2 марта впервые на Средиземном море прошло летно-тактическое учение (ЛТУ) в ближней и дальней зоне ПВО АМГ с отработкой истребителями задач по перехвату самолетов и атакующих крылатых ракет. 6 марта корабли соединения прошли Гибралтар и вышли в Атлантику. На завершающем этапе похода, по прохождении Фарерско-Исландского рубежа, наши корабли приняли участие в командно-штабных учениях СФ. В ходе этих учений на одном из Су-33 (М. Ф. Савицкий) произошел частичный отказ одного двигателя. В условиях отсутствия запасных аэродромов пилот сумел с первого захода посадить аварийную машину на палубу «Кузнецова» (позже за это он был удостоен звания Героя России). 22 марта 1996 г. ТАВКР ошвартовался у своего причала в Видяеве.

Всего за время похода кораблем было пройдено более 14156 миль, выполнено 524 полета самолетами и 996 вертолетами, фактически перехвачено 12 воздушных целей, обнаружены две иностранные ПЛ, отработаны учебно-боевые задачи по двум своим ПЛ, успешно проведены ракетно-артиллерийские стрельбы, в том числе главным ударным комплексом. Первый выход «Кузнецова» на БС в Средиземное море, по воспоминаниям участников, проходил в очень сложных условиях и стоил личному составу большого напряжения сил. Главным образом это касалось электромеханической БЧ. Из-за низкой квалификации личного состава, а также конструктивных недостатков ряда систем, имели место отказы техники. Но самое неприятное к концу боевой службы – из восьми главных котлов в строю осталось два. Домой корабль возвращался, следуя вокруг Британских островов малым ходом, а самолеты летали с ограничениями по взлетной массе, без подвесного ракетного вооружения. 8 апреля 1996 г. крейсер поставили на СРЗ-35 («Севморпуть») для прохождения усиленного навигационного ремонта. С помощью ЧСЗ вновь отремонтировали главные котлы с заменой трубок и установили два дополнительных испарителя типа П-4, сняв проблему дефицита котельной воды. После завершения ремонта, с июля 1998 г. ТАВКР обеспечивал боевую подготовку палубной авиации, в августе участвовал в учениях под флагом Верховного Главнокомандующего ВС РФ. С 26 марта по 2 апреля 1999 г. «Адмирал Кузнецов» занимался боевой подготовкой, пройдя за 193 ходовых часа 750 миль. В октябре 1999 г. крейсер обеспечивал в Баренцевом море ЛКИ нового двухместного палубного учебно-боевого самолета Су-27КУБ. Первые посадка и взлет с палубы состоялись 6 октября (В. Г. Пугачев и Р. Кондратьев), а 7 октября Пугачев вновь посадил Су-27КУБ на палубу, место второго пилота занимал Командующий СФ адмирал В. А. Попов. 16 октября Т. А. Апакидзе впервые посадил Су-33 на палубу «Адмирала Кузнецова» в условиях полярной ночи.

В общей сложности, за первые 10 лет службы корабль прошел 75 тысяч миль. По ряду причин, прежде всего воздействия влажности и низких температур, небрежности и низкой квалификации личного состава, к 1999 г. вышли из строя один из главных котлов, один ГТЗА и ряд систем и механизмов корабля.

Осенью 2000 г. ТАВКР готовился выйти на БС в Средиземное море, но после ее отмены, в связи с гибелью АПЛ «Курск», был поставлен в ремонт на СРЗ-35. 28 сентября 2000 г. в командование кораблем вступил капитан 1 ранга А. В. Турилин. В мае-июне 2003 г. «Адмирал Кузнецов» прошел докование на СРЗ-82 (Росляково), а в октябре направился в Баренцево море на ходовые испытания, во время которых произошел пожар в главном газоходе. В феврале 2004 г. корабль прямо от причала СРЗ-35, прервав ремонт, выходил в море для участия в стратегической командно-штабной тренировке «Безопасность-2004» для обеспечения показательного выступления корабельной истребительной авиации СФ.

Завершив ремонт, пройдя испытания и отработав положенные курсовые задачи, «Адмирал Кузнецов» (командир – капитан 1 ранга А. П. Шевченко) 27 сентября 2004 г. во главе АМГ СФ под флагом Заместителя Командующего СФ вице-адмирала В. Г. Доброскоченко вышел на учения в Северо-Восточную Атлантику в составе отряда ТАРКР «Петр Великий», РКР «Маршал Устинов», БПК «Североморск» и «Адмирал Левченко», ЭМ «Адмирал Ушаков», танкер «Сергей Осипов», спасательные буксиры «Алтай» и СБ-406. Одной из основных задач учений была отработка взаимодействия кораблей при отражении атак условного противника, а также выполнение корабельными летчиками полетов с палубы авианосца. 24 октября АМГ возвратилась в Кольский залив.