נולד בחיפה בשנת 1924. כבר בנעוריו היה פעיל בארגון 'ההגנה'. לאחר מכן התגייס לפלמ''ח ושרת בגליל העליון ובעמק יזרעאל. מיד לאחר שחרורו ב– 1944, הצטרף לקורס הפלוגה הימית בקיסריה, וכך החלה דרכו הימית.
הוא פיקד על יחידת החבלה הימית עוד לפני קום המדינה. תחת פיקודו התבצעו מספר פעולות נועזות במימי נמל חיפה כגון חבלה באניות גירוש בריטיות וספינות מלחמה.
בן-נון פיקד על פלוגת נמל חיפה, אשר השתתפה עם פתיחת מלחמת העצמאות בכיבוש העיר. לאחר מכן הצטרף לגדוד הרביעי של הפלמ''ח ונלחם באזור ירושלים. בקרב על נבי סמואל נפגע ובמשך מספר ימים אף הוכרז בטעות כחלל.
לאחר החלמתו חזר יוחאי אל הים, ובמסגרת ה'שירות הימי' יצא לפעילות רכש באיטליה. עם שובו ארצה קיבל יוחאי את הפיקוד על יחידת סירות הנפץ. במבצע 'יואב' הטביע כוח מיחידת סירות הנפץ בפיקודו את ספינת הדגל המצרית 'אמיר אל-פרוק' ופגעו קשות בשולת מוקשים שליוותה אותה. על פעולה זו זכה יוחאי בעיטור הגבורה, כאחד מגיבורי תש''ח.
עם איחודן של יחידת סירות הנפץ ושל יחידת הצוללים, התמנה יוחאי לפקד על שייטת 13 עד שנת 1950. אחר כך נשלח לארה''ב ללמוד אדריכלות ימית. בשובו, בשנת 1954, מונה למפקד הפריגאטה אח'י 'מזנק'. בשנת 1955 נשלח לליברפול, ונתמנה למפקד אח'י 'יפו', אחת משתי המשחתות שנרכשו עבור חיל-הים. חודשים מועטים לאחר שובו ארצה עם המשחתת נטל חלק בהכנעת המשחתת המצרית 'איברהים אל-אוואל', יחד עם המשחתת השנייה אח''י 'אילת.
בשנת 1958 חזר יוחאי לפקד על שייטת 13 למשך שנתיים, ובשנת 1960 קיבל מידיו של האלוף טנקוס את הפיקוד על חיל-הים. בעת כהונתו החל חיל-הים לפתח את הסטי''לים ככלי שיט שיחליפו את המשחתות. יוחאי בן-נון היה הוגה רעיון השימוש בטילים במקום בתותחים בחיל-הים.
בשנת 1966 סיים את תפקידו כמפקד-החיל. במלחמת ששת הימים היה בשירות מילואים פעיל והשתתף בפשיטות הקומנדו הימי לסוריה.
בשנת 1968 התמנה כמנכ'ל המכון לחקר הימים והאגמים - בחיפה.
במלחמת יום הכיפורים, עשרים וחמש שנה בדיוק לאחר טיבוע האנייה המצרית 'האמיר פארוק', השתתף יוחאי בפשיטה לנמל ע'רדקה.
האלוף יוחאי בן-נון נפטר ב 10 ליוני 1994 והוא בן 69.