В это время на Дальнем Востоке служил относительно новый ракетный крейсер "Червона Украина". Ему было пять лет от роду. Корабль был хороший во всех отношениях. Все было хорошо, но подводило имя. Республики, в честь которой носил он свое имя, уже давно не было. Тем более что эта республика в своей нынешней ипостаси много сделала для уничтожения бывшего могучего Черноморского флота, да и в судьбе "Варяга" сыграла не последнюю роль. Так или иначе, но начальство посчитало, что негоже в составе флота Российского иметь корабль, который носит имя в честь иностранного государства. Ну, представьте себе - в морях и океанах интересы России представляет крейсер "Червона Украина". Нелепость положения очевидна.
Поэтому в конце 1995 года было принято решение крейсер переименовать. На суд экипажа было представлено четыре названия: "Адмирал Макаров", "Владивосток", "Аскольд" и "Варяг". Экипаж, укомплектованный в Камчатской флотилии, однако не торопился относительно нового названия. Видимо, сильны были традиции, воспитанные ветеранами еще той "Червонки". Многие офицеры и матросы были прямыми потомками тех, кто в годы войны проливал кровь на палубах "старой "Червоны Украины". Были и житейские причины, препятствующие принятию единогласного решения о новом названии корабля. С одной стороны, было похвально, что экипаж так болезненно реагировал на это событие, но, согласитесь, другого выхода у командования просто не было. Корабль надо было переименовывать. Конечно, надо было это сделать сразу же после распада СССР, но тогда об этом никто не подумал, и вот теперь этот процесс происходил очень болезненно для всех.
Между тем командование флота торопило с решением. Там, наверху, не хотели принимать во внимание переживания экипажа по этому поводу. В связи с этим командование крейсера было вынуждено принять волевое решение. И это решение было в пользу названия "Варяг". Так была восстановлена историческая справедливость. Над водами Тихого океана с того солнечного февральского утра начал реять гвардейский Андреевский флаг нашего нового "Варяга". И пройдет с того дня еще немало времени, пока мы, современники, по достоинству оценим это событие в истории нашего флота. И со временем мы с гордостью будем вспоминать тех, кто стоял у колыбели нового "Варяга": это первый командир крейсера капитан 2 ранга Липинский Анатолий Иванович; заместитель командира по работе с личным составом капитан 3 ранга Синевич Андрей Эдуардович и ряд других офицеров крейсера. "Ныне наш гордый "Варяг" несет боевую службу на просторах Великого океана". Корабль успешно выполняет учебные стрельбы, часто выходит в море для решения учебных задач. В 1997, 1999 и 2002 годах крейсер побывал с дружественными визитами соответственно в Южной Корее, Китае и Японии.
