Этот корабль поступил в состав ВМФ с опозданием на три года. В частности, авторы труда «Военно- морской флот СССР 1945-1991» В.П. Кузин и В.И. Никольский объясняют причину задержки следующим: «Генеральный конструктор А.С.Яковлев, как оказалось, без всяких серьёзных обоснований и масштабных исследований предлагает оборудовать «Новороссийск» (третий корабль типа «Киев», заложенный после спуска со стапеля «Минска») так называемыми «газоотводными устройствами», представляющими собой огромные (с переменным диаметром 3-5 м) шахты в палубе, выведенные за борт и отводящие газовые струи СВВП, с целью улучшения их взлётных характеристик. Переделываются заново уже собранные корпусные конструкции, «уродуется» корабль. Но техническая авантюра лопается, как мыльный пузырь. Корабль возвращается в исходное состояние. В результате же этого эксперимента срок его сдачи переносится с 1979 на 1982 г.».
Даже в настоящее время трудно оценить, действительно ли они сорвали постройку последующих кораблей, которые могли бы составить будущее ядро авианосного флота? Однако, как говорится, нет худа без добра. На крейсере «Новороссийск» несколько улучшили бытовые устройства, каюты лётного состава разместили по правому борту, изолировав от помех.
14 мая 1983 г. ТАКР «Новороссийск» покинул Чёрное море и через Средиземное вышел в Атлантический океан. В Северной части Атлантики самолёты Як-38 стали летать значительно увереннее, запуски двигателей срывались не так часто. На корабле в этот период осваивался ВКР. Инструкторами были лётчики- испытатели полковник В. Васенков и подполковник М. Тогохов.
Авиагруппа принимала участие в нескольких учениях, проводимых по плану СФ. С июня по август, во время стоянки ТАКР «Новороссийск» на рейде Североморска, лётчики тренировались во взлётах с коротким разбегом на береговом аэродроме. За 4 мес. с этого корабля выполнено свыше 600 полётов, в том числе проведено 120 ВКР.
17 октября 1983 г. группа кораблей, включающая ТАКР «Новороссийск», взяла курс на ТОФ через Атлантический, Индийский, Тихий океаны в Японское море с заходами в Луанду, Мозамбик, Сокотру, Мадрас, Камрань.
19 декабря 1983 г. в Индийском океане впервые был выполнен ВКР парой самолётов. В период похода было организовано дежурство двух пар самолётов в «готовности к вылету», произведено несколько перехватов иностранных самолётов.
27 февраля 1984 г. корабли прибыли на ТОФ. Таким образом, в составе ТОФ оказались два ТАКР.
Ещё в период, когда самолёты Як- 38 демонстрировали свои возможности на ПКР «Москва», решили проверить возможность применения самолётов Як-38 с судов, имеющих ровные площадки. По приказанию главкома ВМФ на контейнеровозе «Агостиньо Нето» в Николаеве было выполнено около двадцати полётов. Для этого на палубе соорудили площадку из бетонных плит размером 25x25 м., с которой выполнено около 20 полётов. Первую посадку 14 сентября 1983 г. выполнил лётчик- инспектор боевой подготовки авиации ВМФ полковник Ю.Н. Козлов, затем полковник Г.Л. Ковалёв, подполковники В.И. Кучуев и др. Полёты проходили до 29 сентября 1983 г. Государственные испытания на контейнеровозе «Николай Черкасов» проводили летчики-испытатели НИИ ВВС В.В. Васенков и А.И. Яковенко.
К исходу 1983 г. можно было подвести итоги усилий по повышению надёжности самолётов Як-38. Выяснилось, что если в начале эксплуатации самолёта Як-38 налёт на один отказ составлял 1,2 ч, что является своеобразным антирекордом, то за первые десять лет эксплуатации надёжность самолёта и его систем удалось довести до 23 ч. на отказ. Это свидетельствовало о наличии определённых успехов. На других самолётах, например, Су-17, также далеко не очень надёжных, налёт на отказ составлял примерно 50 ч.
ВВС СФ и ТОФ прилагали немалые усилия, чтобы несмотря на постоянные доработки, обеспечить регулярные, без длительных перерывов полёты на Як-38. А так как полёты с корабля представляли известную сложность, им уделялось первостепенное значение. В этот период перебоев с поставками топлива ещё не было. Тем не менее добиться систематических полётов с кораблей оказалось невозможным по многим причинам. Самолёты Як-38 базировались на трёх кораблях пр. 1143 «Киев», «Минск», «Новороссийск», вошедших в боевой состав ВМФ соответственно в 1976, 1978 и 1982 гг.
Полёты самолётов Як-38 могли проводиться и проводились со стационарных аэродромов, но это не отвечало их основному назначению – они были корабельными. Полёты с корабля – это существенно более высокий уровень лётного мастерства и отличающаяся психология. С кораблями тоже не все оказалось в порядке. Они довольно часто простаивали: в 1986-1987 гг. ТАКР «Новороссийск» проходил навигационный и доковый ремонты; «Минск» с мая 1986 г. до постановки в усиленный навигационный ремонт 15 апреля из-за выхода из строя покрытия полётной палубы обеспечивал полёты только вертолётов.