בחודש יולי 1942 גויס זכאי לפלמ"ח ונשלח לקורס מפקדי מחלקות בג'וערה, אותו סיים באוקטובר 1942. בינואר 1943 נשלח זכאי לקורס מפקדי סירות של הפלמ"ח בקיסריה. הקורס נמשך כ-10 שבועות והיה בפיקוד יעקב סלומון. זכאי שימש כמדריך ספורט בקורס בנוסף להיותו חניך ואף נבחר לשמש כמזכיר הקורס. באפריל 1943 נפתח הקורס השני למפקדי סירות וזכאי היה אחד המדריכים בו. משתתפי הקורס למדו השטת סירות מפרש ומנוע, תחזוקת ציוד ימי, חוקי שיט בינלאומיים, מטאורולוגיה ודגלי הקוד הבינלאומי. דגש מיוחד הושם על ארגון המעפילים והורדתם מהאוניות לחוף. האקונומית של קיבוץ שדות ים הייתה חנה סנש וזכאי, כמזכיר הקורס, היה בקשר ישיר איתה.
מפקד הפלמ"ח, יגאל אלון, החליט שכל אנשי הפלמ"ח יעברו קורס ימי קצר של שבועיים כדי שיוכלו לסייע במבצעי הורדת מעפילים בהם נדרש כח אדם רב. ואולם, מטעמי העדפה בין מפלגתית, נשלח זכאי לפקד על מחלקה בקיבוץ תל יוסף במסגרת פלוגה ד'. בסתיו 1943 עבר זכאי עם המחלקה לגבעת ברנר והמשיך בתפקיד זה עד סוף השנה.
המחלקה הימית.
במטה הפלמ"ח התגבש הצורך במסגרת ימית נפרדת ובראשית שנת 1944 הוקמה המחלקה הימית של הפלמ"ח במסגרת פלוגת המטה. כוח האדם של המחלקה כלל את מסיימי שני הקורסים למפקדי סירות אליהם הצטרפו בוגרי אגודות ימיות ומספר חיילים יהודים מהצבא הבריטי. המחלקה התארגנה בנמל חיפה שנשלט על ידי הבריטים והועסקו בו ערבים רבים, והכוונה הייתה שאנשיה יעבדו בנמל ויתאמנו בעבודה ימית מעשית. זכאי מונה כמפקד המחלקה הימית ועיקר משימתו הייתה לשמור על האינטרסים היהודים בנמל ולהגן על העובדים והרכוש היהודי בו. חלק מאנשי המחלקה עלו על אניות סוחר וספינות דיג כתחליף לעבודתם במשק. נוכחות קבוצת בחורים צעירים שינתה את המאזן בנמל ונתנה הרגשת ביטחון לעובדים היהודים.
במקביל נעשו הכנות ותוכננו נקודות הנחתה לקבלת אוניות מעפילים בחופי ישראל. פיקוד המחלקה חזר לקיסריה לאימונים וממנה יצאו בסירות דיג לערוך מיפוי טופוגרפי של חופים מתאימים להנחתת מעפילים.
אוניות המעפילים היו מאוישות בצוות מקצועי שהיה צוות זר, רובו ככולו, כולל רב החובל. הוברר שיש צורך שבין מלווי האוניות מטעם ההגנה יהיה בעל מקצוע הבקיא באמצעי ההנעה ומערכות ההשטה של הספינות. לצורך הכשרת בעלי מקצוע כאלה נפתח בבית הספר למקצועות המלאכה ע"ש לודוויג טיץ בקיבוץ יגור קורס למכונאות ימית, והנושאים העיוניים נלמדו בבית הספר בסמ"ת בחיפה. זכאי נשלח ללימודים בקורס זה, אך הוא ראה עצמו כמתאים יותר לתפקידי פיקוד. המחלקה הימית הייתה כפופה לגדוד הרביעי ומפקדו, שמעון אבידן, השתכנע חלקית מדבריו של זכאי ומינה אותו להיות מפקד הקורס למכונאות ימית. בוגרי הקורס הופעלו כמלווים ומפקדי אוניות והכשרתם במכונאות ימית נתנה להם ידע וביטחון.
בתחילת שנת 1945 התקיים קורס חובלים ראשון בבית הספר הימי בחיפה. זכאי צורף לקורס כחניך מן המנין. המדריך הראשי בקורס היה שמואל טנקוס. בקורס הוקנה ידע תאורטי ומעשי בהשטת אוניות ברמה של חובל שני בצי הסוחר. כן הוחדרו נושאי ההעפלה והיחס למעפילים. לאור הגידול הצפוי באוניות מעפילים הוחלט באפריל 1945 להגדיל את מספר האנשים ולארגנם במסגרת חדשה. פלוגה י' בגדוד הרביעי של הפלמ"ח הוגדרה כפלוגה הימית – הפלי"ם. בסיס הפלוגה הוקם בקיבוץ שדות ים וזכאי מונה למפקדה הראשון. הוא פיקד גם על הפלוגה בשדות ים וגם על שלוש המחלקות שנמצאו בקיסריה, בגבעת ברנר, בקיבוץ מעברות ועל היחידה בנמל חיפה. הפלוגה שכללה בתחילה 45 איש הוגדלה וקוים קורס רביעי למפקדי סירות.
זכאי זיהה בשלב מוקדם את הפוטנציאל המנהיגותי של יוחאי בן-נון והטיל עליו את החבלה באוניות הצי הבריטי בנמל חיפה. מתוך הפלי"ם קמה יחידת חבלה ימית שמטרתה פגיעה בכלי השיט הבריטיים שפעלו למניעת הגעת המעפילים.
אניות המעפילים החלו להגיע ואנשי הפלי"ם עסקו בהורדת המעפילים. בחודש אוגוסט 1945 הגיעה לחוף קיסריה אוניית המעפילים דלין (אוניית מעפילים), בפיקוד ישראל חורב ורב החובל אנריקו לוי. דלין פרקה את העולים ויצאה חזרה לאירופה עוד באותו הלילה. אחריה הגיעו שש ספינות נוספות שלא נתפסו על ידי הבריטים.
באוקטובר 1945 הוקמה תנועת המרי העברי, ואנשי הפלוגה השתתפו בכמה מפעולותיה. הבולטת בהן הייתה ליל הרכבות (1 בנובמבר 1945), במהלכו טיבעו אנשי הפלי"ם שלוש סירות משמר בריטיות, שתיים בחיפה ואחת ביפו, שהופעלו כחלק ממערך ההסגר על חופי ישראל מפני כניסת מעפילים. בחיפה פיקד על המבצע יוחאי בן נון וביפו ביצעו את הפעולה יוסף הראל וזלמן כהן; בשני המקרים הגיעו החבלנים לסירות, צללו מתחת לסירות הבריטיות והצמידו אליהן מטען חומר נפץ בעל מנגנון השהייה. זכאי היה מעורב אישית בהבאת המוקשים לחבלה בספינות בחיפה. ניסיונות החבלה בחיפה לא עלו יפה בגלל הלשנה לבריטים.
פעילותו במוסד לעלייה ב'.
אנשי הפלוגה הימית צורפו כמלווים לספינות המעפילים וזכאי, כמפקד הפלוגה, שאף להתנסות בכך גם הוא. לאחר שפנה למפקדיו בפלמ"ח ודרש לצאת כמלווה קבע יגאל אלון במאי 1946 כי זכאי יצא לצרפת, משם ילווה אנייה בדרכה ארצה ויחזור לפקד על הפלוגה הימית.
מכיוון שזכאי הופיע ברשימות המבוקשים של המודיעין הבריטי הייתה יציאתו מארץ ישראל חייבת להיעשות בהסתר. הניסיונות להצטרף לאניות הנוסעים בנמל חיפה לא התממשו ולכן הועלו זכאי וחברו בצלאל דרורי כנוסעים נסתרים באוניית המשא עתיד של חברת חברה לשירות ימי עתיד, שהפליגה לנמל ג'נובה, באיטליה, אליה הגיעו באוגוסט 1946. השניים הוברחו מהנמל למחנה הפליטים שהיה בעיר ושם נפגשו עם לובה אליאב. מרכז המוסד לעלייה ב' היה במילנו בניהולו של יהודה ארזי ועדה סירני כעוזרתו. בניגוד לתוכנית המקורית, על פיה היה זכאי אמור לצאת באונייה מצרפת ולחזור לישראל, הודיע לו ארזי כי על דעת מפקדיו בפלמ"ח הוחלט כי יישאר באיטליה ויסייע לארגון פעילות ההעפלה.
מחנה א' של המוסד לעלייה ב' נמצא בוילה פזנה בקרבת מג'נטה, מערבית למילאנו. המחנה שכן בטירה ישנה שהייתה שייכת לרוזן איטלקי, שהעביר אותה לשימוש המוסד לעלייה ב' כדי לכפר על שיתוף הפעולה שלו עם הפשיסטים. הטירה שוקמה והאתר היווה מחסן עיקרי לריכוז אמצעי הלחימה שנאספו באירופה במגמה להישלח לארץ ישראל. במקום הופעל בית מלאכה ליצור ערסלים, תיקים ומזרנים עבור ספינות המעפילים, ונמצאו בו מחסנים מוסתרים באדמה של ציוד, דלק ומזון, עבור אותן ספינות.
זכאי היה מפקדו השני של "מחנה א'". הוא ארגן את אספקת המזון שהייתה בדרך כלל מתוכננת להפלגה של שבועיים ותכנן את אחסונו באונייה כך שינוצל בדרך היעילה והמדויקת ביותר. הוא תכנן גם את העברת המזון והציוד לאוניות, כמו גם את העברת הנשק (בנפרד) כדי שיוסתר באונייה.
כח העבודה במחנה היו כ-80 פליטי שואה צעירים שסלדו ממשמעת. זכאי החדיר להם מנהגי סדר על ידי דוגמה אישית. את הנוער במחנה לימד עברית תנ"ך ונושאים הקשורים לארץ ישראל. בעת שהותו באיטליה על אף עבודתו המאומצת הצליח לחוות את חיבתו למוזיקה. בכסף שחסך רכש כרטיסים לאופרות במילנו בניצוחו של ארטורו טוסקניני שחזר מגלות שנכפתה עליו במלחמת העולם.
בדצמבר 1946 הטיל יהודה ארזי על זכאי לצאת לנמל לה-ספציה ולהכין להפלגה את האונייה אלברטינה, ששימשה להעברת מעפילים בים לספינות אחרות. התוכנית הייתה לצאת לכמה ימים ולחזור, אך בסופו של דבר נותר זכאי בלה ספציה עד פברואר 1948, מועד תום שירותו באיטליה. תפקידו היה לתכנן ולפקח על ביצוע השינויים הנחוצים באניות למשימת הובלת המעפילים. רב החובל האיטלקי מריו קנדה שימש כעוזרו וכמתורגמן. העבודות נעשו במספנה פורטו ונרה, שם הוכנו מספר אוניות קטנות.
בין האוניות שהגיעו לפורטו ונרה הייתה האונייה האמריקאית פרזידנט וורפילד, שהפכה לאוניית המעפילים אקסודוס בה הופתע זכאי לפגוש את ידידו רב החובל יצחק (אייק) אהרונוביץ'. זכאי וצוותו הסבו את האונייה לקליטת 4,530 מעפילים וכאשר נאלצה האנייה לעזוב את איטליה עבר זכאי עמה לפורט דה בוק בצרפת עם אנשי המספנה האיטלקים והמשיך בביצוע ההכנות לפי התכנון המקורי.
זכאי, אשר רצה לחזור לארץ ישראל כמלווה על "אקסודוס", התבקש להכין את אוניית המעפילים פאן קרסנט לקליטת 7,500 מעפילים, במספנה בוונציה תחת סיפור כיסוי כאילו האונייה עוברת הכנות להובלת כבשים מאוסטרליה. למרות ההסוואה זיהו הבריטים את מטרתה האמיתית של האונייה. לקראת ההפלגה הדביקו הבריטים מוקש בחרטום האונייה שתוכנן להתפוצץ בים הפתוח ולהטביעה. האנייה התעכבה בנמל והפיצוץ גרם לשקיעה ליד הרציף. תיקון האנייה נעשה באיטליה תחת מעקב בריטי ובסוף שנת 1947 יצאה "פאן קרסנט" מוונציה לנמל הרומני קונסטנצה, שם הושלמו ההכנות ליציאה.
גם הפעם קיווה זכאי להפליג לארץ עם "פאן קרסנט" כמלווה, אך שוב הוטלה עליו משימה חדשה: עדה סירני, שקיבלה באפריל 1947 את הפיקוד על המוסד לעלייה ב' באיטליה מיהודה ארזי נדרשה להוציא במהירות אוניית מעפילים על מנת שתגיע לארץ כהפגנה מול ועדת אונסקו"פ. סירני דרשה מזכאי להכין את הנחתת אף-על-פי-כן ששוחררה ממעצר איטלקי כאוניית מעפילים. זכאי הכין את הנחתת במפרץ גאאטה צפונית לנאפולי והיא יצאה לדרכה בסוף הקיץ.
בספטמבר 1947 חלה זכאי בדלקת ריאות קשה, ממנה התאושש רק בתחילת 1948. בכך הסתיימה פעילותו של זכאי באירופה והוא שב לארץ בפברואר 1948 דרך נמל חיפה כשהוא נושא דרכון פלשתינאי של יהודה בורשטיין שכבר חזר לארץ.
על פעילותו בתקופה שקדמה להקמת המדינה קיבל זכאי אישור לענידת אות ההגנה.
צה"ל - חיל הים.