К концу ноября 1991 г. процесс распада СССР приобрел необратимый характер (на 1 декабря были назначены выборы президента Украины и референдум в поддержку акта о государственной независимости этой республики, принятого Верховной радой 24 августа 1991 г.), госиспытания самолетов прекратили, и дальнейшее пребывание «Кузнецова» в Черном море теряло смысл. Стремясь спасти ТАВКР, главком ВМФ адмирал В.Н. Чернавин принял решение о срочном переводе корабля на Север, к месту постоянного базирования. Заранее определялась конкретная дата прохождения Гибралтарского пролива – 5 декабря 1991 г. В штабе Черноморского флота предлагали отправить на Северный флот вместе с «Кузнецовым» также большие противолодочные корабли проекта 1134Б «Очаков» и «Керчь» как наиболее современные, но по ряду причин это не было сделано.

Обеспечение перехода возлагалось на первого заместителя командующего Северным флотом вице-адмирала Ю.Г. Устименко, срочно прилетевшего в Севастополь. На борту «Кузнецова» также находился председатель Постоянной комиссии государственной приемки кораблей ВМФ вице-адмирал А.М. Устьянцев, поддерживавший связь с главкомом. Для обеспечения безопасного прохода «Кузнецовым» турецких проливов командующий Черноморским флотом вице-адмирал И.В. Касатонов заранее выслал к Босфору спасательный буксир «Шахтер».

И хотя о дате ухода корабля было известно заранее, не обошлось без спешки. Вечером 1 декабря Ю.Г. Устименко прибыл катером на борт стоявшего на внешнем рейде крейсера и приказал командиру срочно сниматься с якоря, несмотря на некомплект личного состава, главным образом офицеров и мичманов, оставшихся на берегу. На борту находились представители гарантийной команды от промышленности, а также 15 летчиков и 40 техников 100-го авиаполка, переходивших на Север. В 23 ч. 40 мин. «Кузнецов» дал ход и в охранении БПК «Скорый» и сторожевого корабля «Безукоризненный» вышел в море. На рассвете корабли были перед входом в Босфор, где их ожидал буксир «Шахтер».

Существует версия, что военный атташе США в Анкаре получил директиву воспрепятствовать проходу «Кузнецовым» турецких проливов хотя бы на сутки, но не успел (зато в 2001 г. это получилось в отношении его близнеца, проданного Китаю недостроенного «Варяга», целый год ждавшего в Черном море разрешения местных властей).

В сопровождении «Шахтера» ТАВКР прошел турецкие проливы, где несколько матросов хотели бежать, сбросив с кормы крейсера спасательный плотик и пытаясь достичь на нем турецкого берега, но были подняты на буксир и возвращены на корабль. В сопровождении турецких, а затем греческих, итальянских, французских и испанских кораблей, сменявших друг друга, а также авиации стран НАТО «Адмирал Кузнецов» направился к Гибралтару.

Кроме кораблей непосредственного охранения, обеспечение перехода авианосца до границы зоны ответственности Черноморского флота – меридиана 08°58' западной долготы – возлагалось на находившуюся в Средиземном море 5-ю оперативную эскадру (ПКР «Москва», БПК «Сдержанный», танкеры «Иван Бубнов» и «Борис Чиликин», подводные лодки Северного флота и плавмастерская ПМ-9). В прикрытии ТАВКР участвовал и эсминец «Безбоязненный», осуществлявший межфлотский переход с Балтики на Тихоокеанский флот (корабли разошлись ночью 5 декабря в западной части Тунисского пролива на дистанции 20 миль).

Уже в Эгейском море на ТАВКР была отмечена вибрация третьей машины. Позже выяснилась причина – сорванная штормом и намотавшаяся на гребной винт рыболовная сеть. Движению это особо не мешало, поэтому так и шли до самого Гибралтара, где во время двухдневной стоянки и приема топлива с танкера «Иван Бубнов» корабельные водолазы ножами срезали сеть, освободив винт.

За Гибралтаром в охранение «Адмирала Кузнецова» вступили сторожевые корабли «Бдительный» (Балтийский флот) и «Задорный» (Северный флот).

Там же корабли разошлись с американской авианосной ударной группой во главе с новейшим атомным авианосцем «Джордж Вашингтон», следовавшей из Норфолка в Средиземное море. Американцы приступили к облетам нашего ТАВКР, фотосъемке и замерам его физических полей. «Кузнецов» в ответ передал сигнал «Провожу учения», увеличил ход до 24 узлов и поднял в воздух оба спасательных вертолета Ка-27ПС (самолетов на борту во время перехода не было). А «Задорный» попутно поднял с воды один из сброшенных американскими вертолетами радиогидроакустических буев. В районе 64-й параллели «Бдительного» сменил эсминец Северного флота «Безудержный».

Корабль шел постоянным 12—14-узловм ходом, не считая кратковременного увеличения скорости за Гибралтаром. Замечаний к работе котлов и турбин при переходе не было. После ухода американцев отряд советских кораблей сопровождали сначала британский, а затем норвежский фрегаты; от мыса Нордкап и до самого входа в Кольский залив за отрядом следил норвежский разведывательный корабль «Марьятта».

21 декабря «Адмирал Кузнецов» прибыл на Северный флот и был включен в состав 43-й (Атлантической) дивизии ракетных крейсеров с базированием в поселке Видяево.

В конце 1991 г. 5-я оперативная эскадра была расформирована. Советские корабли покинули воды Средиземного моря. Начались распад Союза и агония Черноморского флота.

Гимн Средиземноморской эскадры ВМФ

(Слова В.В. Заборского. Исполняется на мотив марша «Прощание славянки» композитора И.Н. Агапкина.)

За Босфором и Дарданеллами

Вдалеке от родимой земли

По Средиземноморским просторам

Боевые идут корабли.

Гордо реял на этих просторах

Наш священный Андреевский флаг,

И не раз мощь Российского флота

Испытал своей шкурою враг.

И снова в поход эскадра идет

По волнам, под водой,

Стальною грозной чередой,—

Эскадра Пятая, врагом проклятая,

Всегда готова в смертный бой!

Здесь бродил Одиссей после Трои,

Одолев все интриги богов.

Здесь победами флота Россия

Скалить пасть отучила врагов!

Спиридов и Орлов,

Сенявин, Ушаков

Врагов здесь били,

Жгли и топили,

Чтоб знали русских моряков!

Чтоб дрожали!

И уважали

Наш доблестный Российский флот!

Снова вьется на этих просторах

Наш военно-морской гордый флаг!

Мощь и силу ударов эскадры,

Нам прикажут, – изведает враг!

Путь знает Шестой флот,

Придет его чред!

Мы по приказу

Ударим сразу—

Он от возмездья не уйдет!

Пусть помнит Чесму—

Ему известно,

Как там пылал турецкий флот.

Мы наследники доблести предков,

Чтим заветы мы дедов, отцов—

Ради славы и чести Отчизны

Не щадить ни себя, ни врагов!

И враги пусть злорадно считают—

Семь минут уцелеть нам дано!

Их расчеты нас не запугают,

Не уйдем мы покорно на дно!