הספינות הפליגו משרבור בשעה 02:30, בליל חג המולד, 25 בדצמבר 1969. הספינות לא הדליקו אורות, ויצאו מהפתח הראשי של הנמל. לאחר התרחקות מהחוף פנו ועברו את איי התעלה. הן הפליגו בשני טורים: את הטור הראשון הובילה ספינת הדגל אח"י "סופה", ואחריה אח"י "חץ" ואח"י "חנית". לשמאלן הפליגו שתי הספינות הנותרות, אח"י "חרב" מובילה ואחריה אח"י "געש". כאמור לעיל, על סיפון אח"י "סופה" המובילה היה אל"ם הדר קמחי, מפקד המבצע, ועל סיפון האונייה האחרונה, אח"י "געש", היה סגן מפקד המבצע, סא"ל עזרא קדם (כריש). שתי ספינות אלה היו היחידות שהיו בעלות מכשיר קשר בתדר גבוה, שאפשרו קשר עם מפקדת חיל הים בישראל. בשאר הספינות היו מכשירי קשר בתדר גבוה מאוד, שאפשרו תקשורת בין הספינות בטווח קצר של עד 24 קילומטרים. בנוסף למכשירים אלה, הביאו עמם אנשי הצוות שהגיעו מישראל מכשירי קשר ניידים ביתיים (המכונים walkie-talkie). מכשירים אלה מופעלים על ידי סוללות ולהם טווח קליטה עד שני ק"מ. מכשירים אלה שימשו לקשר בין הספינות. בתורני הספינות הותקנו פנסים ונקבעו סימנים מוסכמים לאיתות אור.
כל הספינות, מלבד אח"י "חץ" (שהושקה אחרונה, ולכן לא היה זמן להתקין בה), צוידו במכ"ם "קלווין יוז" בריטי המשמש את אוניות הסוחר לניווט. בספינות הסער הקודמות הותקן שולחן מי"ק המחובר למצפן ומד דרך, ויכול היה לתת ניווט מחושב. ואולם, בחמש הספינות הללו לא הותקן שולחן כזה, מכיוון שיצרנית השולחן, "נדינסקו" מהולנד, הביאה לתשומת לב כי פריט זה נחשב לציוד המיועד לספינות מלחמה, ולפיכך אם היה מגיע לצרפת היה נכנס למסגרת האמברגו.
תוכנית מסלול השיט כללה, מהיציאה הראשית של נמל שרבור, הפלגה בקטע קצר לכיוון צפון כדי להתרחק מהחוף, ולאחריו קטע ארוך יותר לכיוון מערב כדי להקיף את כף דה לה הייג ואת איי התעלה. הקטע הבא היה בכיוון דרום מערב עד הכניסה למפרץ ביסקאיה. מזג האוויר ששרר בעת היציאה לא אפשר ניווט אסטרונומי, וכדי להבטיח מגע מכ"ם עם החוף נלקח כ-10 מעלות מזרחה יותר, במגמה לגלות את פורט בארס בחוף ספרד מול החרטום, ואז להקיף את חופי ספרד ופורטוגל במרחק ראייה ביום ואבחנת המגדלורים בלילה כנהוג באוניות קטנות.
מהלך ההפלגה.
זמן קצר לאחר היציאה התקלקל מכשיר המכ"ם של אח"י "חרב", והקשר עם הספינות האחרות התקיים באמצעות מכשיר בעל טווח מזערי. קצין המשמרת עקב אחר האורות של הספינות מלפנים, אך מפקד הספינה, חיים שקד, חש שהספינה שינתה מסלול. הסתבר שקצין המשמרת בגשר לא הרגיש שהוא עוקב בטעות אחר אורות של אונייה שהפליגה לצרפת. שקד שינה מסלול והגביר מהירות עד שמצא את הספינות האחרות והשתלב למקומו במבנה.
הקצין הראשון בא/מ "נהריה", שהיה במשמרת בין השעות 4 ל-8 בבוקר, דיווח לרב החובל מאיר פרויס שהבחין באורות חמש ספינות דיג מהירות שעברו מרחוק ואחת מהן גם נצנצה בזרקור. הקצין הראשון היה הולנדי ולא תודרך לצפות לכך, ולכן לא ראה חשיבות להעיר את רבי החובלים בזמן הגילוי. במהלך היום הועברה הוראת גמר כוננות לא/מ נהריה והיא חזרה לנמל אנטוורפן.
במהלך התנועה במפרץ ביסקאיה היו גלי גיבוע גבוהים ממערב וגלי רוח חזקים מצפון. הגלים לא אפשרו שמירת מדויק כי החרטום התרוצץ ימינה ושמאלה כ-15 מעלות לכל צד. המהירות המתוכננת הייתה 20 קשר (כ-37 קמ"ש) אך עקב העליות והירידות מהגלים לא היה ברור כמה דרך נעשית באמת. רק בקרבת החופים ניתן היה לנווט על סמך תמונת המכ"ם.
תדלוק ראשון.
הבריטים בגיברלטר נהגו לבקש זיהוי ולדווח לחברת לוידס על כלי השיט במעבר. לכן תוכנן התדלוק להיעשות לפני המעבר במצר גיברלטר. במקום שנקבע לתדלוק היה ים גלי, ורב החובל אמנון תדמור מצא מקום שקט יותר. הוא עגן קרוב מאוד לחוף במפרצון ליד כפר דייגים, מערבית לכף טרפלגר. במקום עוברות אוניות רבות ולפעמים גם עוגנות כך שעגינת האונייה לא משכה תשומת לב.
ב-26 בדצמבר, בחצות לילה, התקיים המפגש במקום העגינה, כאשר הספינות במרחק כ-300 מטר מהחוף. ראשונות לתדלק היו אח"י "סופה" ואח"י "חץ". לאחר שהאיר היום, יצאה מהחוף סירת דיג ועליה אדם במדים, שרשם את פרטי האונייה והספינות, אך לא שאל פרטים ולאחר שעה עזב. מאוחר יותר הגיע מסוק שחג בגובה גשר האנייה ועקב מקרוב מאוד על הפעילות. רב החובל הרים עוגן ו"לאה" התרחקה לכיוון הים תוך המשך התדלוק, כאשר הים השקט הקל את העבודה. הזמן הכולל של התדלוק היה 17 שעות.
חשיפה מוקדמת מהצפוי.
תוכנית המילוט נבנתה כך שיעד ההפלגה יישאר חסוי. מסיבה זו הפליגו הספינות בליל חג המולד, כדי שמעט אנשים יראו אותן. אמיו הצליח לעכב את פרסום הידיעה בעיתוני שרבור עד למחרת חג המולד, אם כי הוא עצמו דיווח כבר באותו יום למשטרה כדי לעמוד בדרישות החוק. כמעט שתי יממות עברו עד שהעובדה כי הספינות עזבו נקלטה בממשלת צרפת, אך קוראי הדיילי טלגרף בלונדון קראו כבר בעיתון שיצא בשבת, 27 בדצמבר את הסקופ כי לשאלות כתבים ענה מרדכי לימון שאינו יודע דבר; איש המכס בשרבור סיפר ש ואולם, מפגש התדלוק ליד החוף הספרדי נחשף, ואז התברר כי כיוון תנועת הספינות הוא לים התיכון ולא לים הצפוני. התקשורת מלאה דיווחים וגם בעיתוני הארץ פורסמו כתבות.
תדלוק שני.
הספינות יצאו יחד ועברו את מצר גיברלטר. הן לא ענו לדרישת הזיהוי, אך קיבלו ברכת דרך צלחה מהבריטים. בחצות ליל 27 בדצמבר דיווח ה-BBC כי הייתה זאת דרכם של הבריטים כדי לצאת ידי חובת דיווח. למחרת שודרו תמונות בטלוויזיה הבריטית והחלה מהומה תקשורתית עולמית. ב-28 בדצמבר חג מעל הספינות מטוס סיור צרפתי מדגם , והיה ברור שהצרפתים יודעים את מקום הספינות ואת נתיב ההפלגה שלהן.
א/מ "תמר" עוכבה באזור עד ששוחררה בשעה 06:50, ושלוש שעות מאוחר יותר שוחררה גם א/מ "לאה" להמשיך בדרכה. מצב הים החל להיות שוב קשה. בקטע זה נעשתה החלפת מסנני דלק למנועים; לצורך ההחלפה הושבת בכל פעם מנוע אחד שלו הוחלף מסנן הדלק, והספינות נעו באמצעות שלושה מנועים במהירות 20 קשר. להמשך השיט נבחר נתיב קרוב לחופי אפריקה. מפקד ההפלגה סבר שהאיום בשלב זה בא בעיקר מהצי הצרפתי מצפון.
אוניית הנוסעים א/מ "דן" הקדימה ביממה להגיע לאזור התדלוק. כאמור, רב החובל יוסף דרור הציע לקיים את התדלוק בקרבת האי למפדוזה, שם יש תנועה מופחתת של כלי שיט. המפגש התקיים בבוקר 29 בדצמבר, והתדלוק החל בשעה 08:30. בשעה 20:30 הגיעה לאזור ספינת ביון סובייטית שעקבה מקרוב אחר הנעשה. התדלוק נמשך עד שעה 22:30.
פעילות המצרים והסובייטים.
המידע התקשורתי הרב הגיע לידיעת חיל הים המצרי. היועצים הסובייטיים בצי המצרי הציעו למצרים להשתלט על הספינות בדרכן מתוך ידיעה שאינן חמושות. המקום שהומלץ ליירוט בין תוניסיה לסיציליה, והמצרים שיגרו משחתת מסדרת סקורי מאלכסנדריה וכלי שיט נוספים לבצע זאת. במהלך ההפלגה נתקלה המשחתת בקשיים טכניים, והיא חזרה לנמל. אפשרות נוספת שנשקלה הייתה תקיפת הספינות הישראליות על ידי ספינות טילים מצריות מפורט סעיד, אך גם משימה זו לא יצאה לפועל עקב מצב הים הקשה לספינות קטנות, או – לפי הרישום המצרי – עקב התנועה המהירה של הספינות. הפלגת המשחתת וחזרתה לאלכסנדריה התגלו על ידי המודיעין הימי והועברו לידיעת מפקד ההפלגה.
על מנת להקטין סיכוי למפגש עם הצי המצרי נשלחו אח"י געש ואח"י חץ לדרכן מיד כשסיימו את התדלוק. ביציאה המזרחית מהים האגאי עברו הספינות משני צידי האיים קסו וסקרפנטו.
ספינת ביון של הצי הסובייטי עקבה אחרי התדלוק בלמפדוזה. מעבר לכך לא הייתה היערכות מיוחדת בשייטת הסובייטית בים התיכון.
מזרח הים התיכון.
בשל תקלה נאלצה אח"י חץ לכבות מנוע אחד, ומפקד המבצע הדר קמחי החליט לפצל את הכוח, ושלח את זוג הספינות ואח"י געש בפיקוד סא"ל עזרא קדם (כריש) לדרך מיד כשגמרו לתדלק. שלוש הספינות הנותרות יצאו לדרכן שמונה שעות מאוחר יותר, כשגמרו לתדלק. אף כי הים היה גבוה נעו הספינות במהירות 30 קשר (כ-55 קמ"ש). הכוח התאחד בדרום הים האגאי מצפון לכרתים. בינתיים החלו מספר מנועים להוציא אדי מים. מחשש שאובדן מים יחייב לכבות מנועים, בדק קמחי את מיקומן של אוניות סוחר ישראליות באזור, לצורך גרירת הספינות בעת הצורך. יציאת הספינות כבר הייתה ידועה בשלב זה, ותחנת החוף בחיפה ביצעה את הבדיקה ויצרה קשר עם שבע אוניות שכולן דווחו ברצון את מיקומן ונתיב תנועתן והתנדבו לסטות מנתיבן ולהגיש ללא תשלום כל עזרה שתידרש. התגובה הייתה מעודדת, אך בסופו של דבר לא היה צורך בגרירה.
רשויות הצי ביוון פרסמו הודעה שממנה השתמע כי יאותו לתדלק את הספינות. ממלא מקום ראש הממשלת יוון אף בירך את הפעולה הישראלית בלא לנקוב בשמות. בעת ההפלגה בים האגאי עברו שתי ספינות מלחמה לא מזוהות ליד הכוח. מלחמת ההתשה הייתה בעיצומה, ובמפקדת חיל הים הועלה חשש ממארב צוללת של חיל הים המצרי ביציאה מהים האגאי. לאור מצב הים הסבירות לכך הייתה נמוכה, וגם בים שקט ספינת סער מהווה מטרה קשה מאוד לפגיעה בטורפדו. הספינות נפגשו מחדש מצפון לכרתים משם לקחו מזרחה עד קפריסין ומשם פנו לחיפה.
זוג מטוסי פנטום של חיל האוויר נשלח לפגוש את הספינות ולאבטחן, ומטוס נורד סייר בגזרה דרומית יותר. יציאת ספינות שייטת ספינות הטילים מחיפה למפגש עם ספינות שרבורג בוטלה אם מחמת מצב הים ואם לצורך הקטנת פרופיל.
הספינות בחיפה.
ב-31 בדצמבר 1969 אחר הצהריים הגיעו הספינות לחופי ישראל. הספינות עוכבו במרחק מהחוף עד רדת החשיכה, ורק בשעה 18:30 נכנסו לנמל הקישון שבחיפה. כדי להוריד את המתח ביחסי ישראל–צרפת נמשך סיפור הכיסוי גם לאחר הכניסה. הספינות נכנסו בלילה כאשר הצוותים בבגדים אזרחיים ושלטי STARBOAT גלויים בצדי הגשר. הן הוצגו כשייכות לחברת נתיבי נפט.