Ярким эпизодом истории корабля стал поход на нем Министра Обороны СССР маршала Жукова на празднование 23 годовщина освобождения Югославии. Решение отправиться на крейсере в Югославию было принято лично маршалом.
Можно предполагать, что выбор командования Черноморским Флотом на крейсер “Куйбышев” (бортовой № 43 в то время), пал не в последнюю очередь потому, что им командовал земляк Маршала (калужанина по происхождению) капитан 1 ранга В.В.Михайлов. С 12 сентября началось подготовка крейсера к походу, корабль полностью был перекрашен, на верхней палубе было заменено изношенное оборудование, были заменены швартовые и леерные устройства, такелаж; обновлены каюты офицеров, салоны и кают компания.
В отряд кораблей, помимо крейсера, входили также эсминцы пр.56 «Бывалый» и «Блестящий». Отряд возглавлял первый заместитель командующего ЧФ вице-адмирал С.Е.Чурсин, а походный штаб - контр-адмирал В.И.Тюняев.
Учитывая крутость Маршала, его желание везде навести порядок и некую нелюбовь к флоту, командование ВМФ весьма серьезно опасалась возможного недовольства со стороны всесильного министра обороны. Подготовку корабля к походу возглавлял первый зам ГК ВМФ адмирал А.Головко
Он же довел офицерам корабля слова ГК ВМФ СССР Горшкова “судьба военно морского флота во многом зависит от вас”, командиру же крейсера сказали “Если у тебя что случиться с Жуковым, мы тебя не спасем”. Так что маршалу стремились угодить в ее просьбах. Заметив широкие брюки на ногах адмиралов, маршал ехидно заметив “что то долго мои приказы доходят до флота”, утром все брюки офицерского состава были приведены к уставу. Потом непривыкший к корабельной музыке Маршал пожаловался—“шумно на корабле, мне трудно работать”. Были остановлены котлы носового эшелона, Трансляция и колокола громкого боя были запрещены,приказы передавались либо устно, либо по корабельном телефонам. На трапы, ведущие на ходовой мостик, были уложены шумопоглащающие маты.
Пакет мер по снижению шума не остался незамеченным, о чем утром маршал с удолетворением и сообщил командиру.
Любое сказанное им слова тут же передавалось в Москву Командованию флота. Замечания маршала фиксировались и по ним принимались решения, так например была изменена форма одежды офицерского и рядового состава на более удобную.
4 октября 1957г. маршал СССР Жуков и сопровождающие его лица прибыли на корабль, после чего в 1500 началось движение отряда. 5 октября по прибытии в б. Золотой Рог крейсер произвел салют наций, стреляла батарея УК №1 правого борта. Корабли отряда приветствовали с берега работники советского посольства. А турецкий морской пост на мысе Шиле семафором передал текст: «Великому маршалу Советского Союза, высокочтимому полководцу Второй мировой войны. Поздравляем и приветствуем Вас с заходом в турецкие воды. Долгих лет жизни и наилучшие пожелания. Счастливого плавания!» А на берегу Босфора, несмотря на дождь, был выстроен турецкий почетный караул…
Интересным добавлением к облику Маршала стало то, что рассматривая берега Босфорского пролива, маршала интересовала не история или красоты этих мест , а возможности использования сухопутных сил в операциях на данной местности. Весьма показателен и тот факт, что самолеты и вертолеты стран НАТО, как правило, жестко опекающие проходящие наши корабли, в этот раз держались на почтительном расстоянии или вообще не появлялись.
6 октября маршал обходил крейсер, общался в кубрике с личным составом, узнав что командир крейсера является его земляком, Г.К.Жуков пригласил его 7 ноября на открытие в своем родном селе Дома Культуры. Потом командование корабля, здраво рассудив, что пушек Маршал в своей жизни насмотрелся, повело его в котельные и машинное отделения, при этом не обошлось без традиционных флотских приколов. Дабы маршал на своей шкуре прочуствовал, каково там нести вахту в машинном отделении, там придержали вентиляцию. Эти отсеки произвел на маршала большое впечатление.
8 октября 1957г. при входе в порт Задар салют наций был сделан более внушительным—темп стрельбы 6 секунд вместо 5, причем первоначально было предложение стрелять главным калибром крейсера ( используя согревательные снаряды), однако из за опасения воздействия ударной волны от 6дюймовых пушек было принято решение стрелять 100мм пушками, но с другим темпом стрельбы в 6 сек.
Покидая корабль, Маршал Советского Союза Г.К.Жуков произнес удивившую всех речь, сказав сперва, что он был плохо осведомлен о флоте, а теперь после похода “Военно-Морской флот, как я убедился в коротком плавании на крейсере Куйбышев, это мощный вид вооруженных сил, и я постараюсь с возвращением в Москву принять надлежащие меры, чтобы Военно-Морской Флот занял достойное место в Вооруженных Силах страны. Я восхищен образцовой дисциплиной, безукоризненным внешним видом моряков, их уровнем подготовки и верностью присяге Советскому народу. Спасибо Вам за это, и я желаю всем дальнейших успехов. Мне было вдвойне приятно еще и от того, что крейсером командует отличный морской офицер, да вдобавок еще и мой земляк.” Экипажу крейсера была объявлена благодарность, ряду офицеров, старшин и матросов Г.К.Жуковым были награждены ценными подарками.