1994 року відбувся похід фрегата «Гетьман Сагайдачний» у Францію. Це був перший вихід українського корабля за межі Чорного моря і перший далекий похід в історії Військово-Морських Сил України. Командиром корабля був капітан 3 рангу Сергій Настенко, командиром походу – капітан 1 рангу Юрій Шалит, досвідчені офіцери, які мали за плечима  великий досвід морської служби та далеких походів. Та й у складі самого екіпажу корабля було досить досвідчених офіцерів і мічманів.

Проте викликала занепокоєння повна відсутність системи тилового та технічного забезпечення в районах майбутнього походу. До того ж корабель лише рік, як увійшов до складу ВМС, перебував на гарантії та мав ще деякі «дитячі хвороби».Саме це підживлювало скептиків стосовно успішності виконання поставлених завдань. Не обійшлося і без провокації росіян. Напередодні виходу командування Чорноморського флоту Російської Федерації силами 102 загону боротьби з підводними диверсійними силами та засобами намагалося  не допустити постановку фрегата «Сагайдачний» та корвета «Луцьк» на швартові бочки  для участі у фестивалі «Зоряний прибій», який проводився 25 червня. Нашим швартовим групам довелося декілька годин сидіти на швартових бочках та охороняти заведені швартові кінці. Російський протидиверсійний катер «окупував»  сусідню бочку і не давав «Луцьку» до неї ошвартуватися. Врешті- решт проблема була розв’язана та на бочках стали два українські та два російські кораблі.

Після ретельної та виснажливої підготовки корабель 26 червня розпочав похід і вже на початку ранку наступного дня втягнувся у протоку Босфор. вечері у Дарданеллах зустрілися перші іноземні бойові кораблі – чотири італійські корвети типу «Мінерва», які прямо посеред протоки продемонстрували нам відмінний морський вишкіл у спільному плаванні – декілька поворотів «усі разом», стрій фронту, пеленгу.
Нарешті український корабель вийшов  в Егейське море і зустрів  корвет ВМС Франції, який навіть гадки не мав, що є така країна Україна і де вона знаходиться.

В Іонійському морі фрегат «Сагайдачний» вперше отримав досвід навчання з кораблем НАТО. Це було досить просте «попутне» навчання (PASSEX) з грецьким фрегатом. Проте на борту «Сагайдачного» був лише один офіцер, капітан 2 рангу Євген Лосев, спроможний працювати з кораблями за стандартами НАТО. Він фактично став першим операційним офіцером українських ВМС і, головне, свій досвід і вміння передав корабельним офіцерам.  У протоці Ла-Манш фрегат «Cагайдачний» та крейсер-вертольотоносець ВМС Франції «Жанна Д’Арк» також провели спільні навчання з посадкою корабельних вертольотів.

Взагалі, весь перехід морем був насичений інтенсивними навчаннями з екіпажем та корабельного вертольоту. Виконувалися також артилерійські стрільби та інші бойові вправи. Корабель вів розвідку та попутний пошук підводних човнів. Десь біля берегів Іспанії фрегат «Сагайдачний»  виявив підводний човен і більше 40 хвилин підтримував з ним контакт, не поганий результат для одиночного корабля.

Український фрегат прикував досить багато уваги з боку сил НАТО. Відбувалися регулярні обльоти корабля літаками базової патрульної авіації: Р3С «Оріон», «Атлантік».

Першим портом заходу був Тулон у Франції. За три дні стоянки корабель поповнив запаси продовольства, води, пального, екіпаж провів регламент та догляд матеріальної частини.
Пройшовши Гібралтарську протоку, Біскай 10 липня у проливі Ла-Манш фрегат «Гетьман Сагайдачний» підійшов на рейд Гавру, на вхід в устя річки Сена. На вхід у Сену чекали своєї черги декілька десятків кораблів та суден, багато всесвітньо відомих вітрильників.  Всі вони прибули на велике свято, морський фестиваль «Армада свободи» (Armada de la liberté) на честь 50-річчя висадки союзних військ у Нормандії. Фестиваль проходив у столиці Нормандії місті Руан. Фрегату «Гетьман Сагайдачний» знадобилося декілька годин, щоб подолати 120 миль річкою Сени та ошвартуватися в порту Руан.

В Руані на корабель прибули командувач ВМС України віце-адмірал Володимир Безкоровайний та Надзвичайний і Повноважний Посол України у Французькій Республіці Юрій Кочубей. Саме завдяки Володимиру Герасимовичу Безкоровайному здійснився цей похід, а Юрій Миколайович Кочубей організував перший офіційний візит українського корабля в іноземну країну.

Фестиваль «Армада свободи» тривав тиждень, з 10 до 16 липня. За цей період його відвідали більше 2 мільйонів людей. І там було на що подивитися – більше 50 кораблів та суден з 21 країни світу. У тому числі більше тридцяти вітрильників, з них найвідоміші вітрильники: чілійська «Есмеральда», колумбійська «Глорія», американський «Ігл», італійський «Амеріго Веспуччі», португальський «Сагреш», польський «Дар Млодежи», норвезький «Крістіан Радіш», німецький «Александр Гумбольт». На святі був присутній і фактичний учасник Нормандської десантної операції у 1944 році, вантажне судно «Джеремі О’брайн» – єдине судно типу «Ліберті», яке зберіглося і спроможно перетнути Атлантику. Україну представляли фрегат «Гетьман Сагайдачний», барк «Херсонес» і козацька чайка «Пресвята Діва Богородиця». Були у Руані і воєнні кораблі з Франції, Бельгії , Бразілії, Великої Британії, Греції, Данії, Іспанії, Нідерландів, Південної Африканської Республіки, і Росії.

Екіпаж «Сагайдачного» прийняв участь у параді на честь національного свята Франції – Дня взяття Бастилії . А футбольна команда українського корабля хоч і не зайняла призового місця на міні-чемпіонаті Світу з футболу, проте отримала Приз симпатій глядачів.

Взагалі фрегат «Сагайдачний» користувався великою популярність. Кожен день  біля його трапу вистроювалися величезні черги на екскурсію кораблем. Імпровізовані концерти, які давав оркестр ВМС України просто на причалі біля корабля збирав багато глядачів. За час перебування в Руані «Сагайдачний» відвідало близько 10 000 людей і практично усі вони не знали про існування України.

Українські військовослужбовці із задоволенням розповідали європейцям про Україну. Вони на власні очі бачили український прекрасний бойовий корабель і розуміли, що в  Європі з’явилася ще одна потужна країна. Національного колориту додавали хлопці з екіпажу козацької чайки. Прямо посеред  Франції, у національних костюмах з пістолями за поясом, з козацькими вусами та оселедцями,  вони робили невеличкі різноманітні виступи. Іноземці мали можливість одночасно бачити і сучасність, і славетне минуле України.

І ще одна подія сталася під час перебування фрегату «Сагайдачний» у Франції. Наших моряків зустріла українська діаспора. Це було дуже важливо. Вперше ми так відкрито зустрічалися з нашими співвітчизниками за кордоном (за радянських часів подібні стосунки були заборонені). Такі зустрічі були дуже теплими та відвертими. Відчувалася велика повага до нас і гордість за нашу країну. Наші співвітчизники проявили традиційну українську гостинність, деякі військовослужбовці були запрошені до дому у гості, багатьом влаштували невеличкі екскурсії у місто. Відчувалася теплота і єдність.
Святкові заходи завершилися, «Сагайдачний» постав гідно в загальному строю свята «Армада Свободи» і, по суті, став візитною карткою країни, підтвердив статус України як морської держави.
Похід тривав 43 доби і завершився 7 серпня 1994 року. Загалом було пройдено 12 тисяч морських миль. Фрегат «Сагайдачний» відвідав три іноземні порти (Тулон, Руан, Гавр), пройшов 7 морів (Чорне, Мармурове, Егейське, Іонійське, Лігурійське, Болеарське, Альборан) та вийшов у Атлантичний океан.

Але головним здобутком походу – був безцінний досвід: підготовки корабля та тривалого плавання, організації зв’язку з віддалених районів Світового океану, всебічного забезпечення діяльності українського корабля в умовах відсутності системи базування, дипломатичного супроводження далекого походу.