אלון ומרבית אנשי "אחדות העבודה" התקשו להתיישר לפי הקו היוני של מפ"ם. הם לא אהדו את ברית המועצות, היו אקטיביסטים מבחינה ביטחונית, הטיפו למדיניות של נקיטת יד קשה כנגד מדינות ערב בנוגע לאיומים על ישראל ועל גבולותיה, ולמדיניות של אי-התערבות במאבק בין הגושים, צעד שימנע מישראל הסתבכות במלחמה הקרה. בכלכלה הם היו קרובים למפ"ם בתמיכה בקו סוציאל-דמוקרטי מלא. כאשר אלון הגיע למסקנה כי אין הצדקה לקיומה של מפ"ם המאוחדת, היה בין יוזמי התפלגות "אחדות העבודה" ממנה.
ההגמוניה של "השומר הצעיר" בעיתון המפלגתי המשותף "על המשמר", הביאה להחלשת קולה של "אחדות העבודה" בו. בעקבות זאת, החליטה מזכירות "הקיבוץ המאוחד", בהובלתו של אלון, להוציא ביטאון פוליטי סדיר של "אחדות העבודה" ובאפריל 1954 הוא החל בהכנות המעשיות להוצאת "למרחב". צעד זה גרם להגשת אולטימטום מצד יריביו במפ"ם. ב-20 באוגוסט כתב אלון במאמר מערכת כי "נפל הפור" והטיל את האחריות לפילוג על "השומר הצעיר".
ב-1954 היה אלון ממובילי פירוק מפ"ם הגדולה, לטובת הקמתה המחודשת של אחדות העבודה - פועלי ציון, שהפכה למפלגה עצמאית ואלון שימש כמזכ"ל שלה.
לאחר "פעולת עזה", פרסם אלון ב"למרחב" ב-4 במרץ 1955 את עקרונותיו הצבאיים-מדיניים: מדינות ערב נמצאות "במצב לחימה" עם ישראל, ומצב זה הופך כל פעולה צבאית ישראלית ללגיטימית, הן מבחינה מוסרית והן מבחינת המשפט הבינלאומי. בניגוד לאומות אחרות, לעם היהודי בישראל אין את האפשרות להיות מובס במלחמה, משום שמשמעותה של תבוסה תהיה כיליון. המסקנה מכך היא שעל ישראל ליזום מלחמה ולא להסתפק ב"התגוננות פעילה" כפי שצה"ל נקט בפעולה בעזה.
חבר הכנסת (כהונה ראשונה) (1960–1955).
לאחר הבחירות לכנסת השלישית ביולי 1955, הפך אלון לחבר הכנסת מטעם "אחדות העבודה" והצטרף לוועדת החוץ והביטחון. לאחר פרסום עסקת הנשק הצ'כוסלובקית-מצרית בספטמבר 1955, החל הציבור הישראלי לתרום מכספו למען קניית נשק לישראל. כדי לארגן ולעודד את זרם התרומות, הוקם "הוועד הציבורי לקרן המגן", ואלון היה אחד מ-16 אישי הציבור שהובילו אותו.
אלון כיהן כחבר הכנסת בשנים 1955–1960, בכנסות השלישית והרביעית, והיה חבר בוועדת הכלכלה, בוועדת החינוך והתרבות ובוועדת חוקה, חוק ומשפט. הוא היה נואם מבוקש לאספות בחירות והביא אליהן קהל רב, אם כי הומוגני יחסית. הוא זכה לפופולריות רבה בקרב ילידי הארץ, אך למרות ניסיונותיו, לא הצליח לחדור ללבם של העולים החדשים יוצאי מדינות ערב, שפחות הכירו אותו כאיש צבא, או שלא הזדהו עם האידאולוגיה שהציג.
באוקטובר 1955 יצא אלון לסיור של חודש במערב אירופה. אנשי "המגבית המאוחדת" סברו שאלון חזק בהסברה מדינית לצורך דיפלומטיה וגיוס כספים. בפברואר 1956 הוא השתתף בצילומי סרט תיעודי על ישראל, של העיתונאי האמריקאי המפורסם, אד מורו, ומספר ימים לאחר מכן, יצא לביקורו הראשון בארצות הברית. במהלך ביקורו, השתתף בראיון טלוויזיוני בהנחיית אד מורו, בו התעמת, באמצעות שני מסכים, עם מוחמד חסנין הייכל, עורך העיתון המצרי "אל-אהראם". הסיור בארצות הברית נמשך כחודשיים, עד תחילת מאי, ומשם המשיך למשימות הסברה והתרמה בדרום אפריקה וביוני 1956 שב לישראל. באוקטובר 1956, שבוע לפני פרוץ מבצע קדש, הצטרף למשלחת חברי כנסת ליוגוסלביה, שנפגשה בין השאר עם טיטו. מיד עם שובו בנובמבר, לאחר תום המלחמה, יצא בהוראת שרת החוץ גולדה מאיר בשליחות מדינית לאנגליה, בשל הקשרים שפיתח עם מפלגת הלייבור, ועסק בהסברה ובגיוס כספים ל"מגבית החירום". בלונדון הציע להבדיל בין מדבר סיני לרצועת עזה וטען כי "אין היא פחות אדמת ישראל מאשר תל אביב עצמה". בתחילת דצמבר טען בכינוס מועצת ההסתדרות כי מבצע סיני "לא היה מלחמת מנע ואף לא מלחמה יזומה", אלא "מבצע התגוננות מובהק". כנץ פוליטי, התנגד אלון יחד עם אנשי מפלגתו לנסיגת צה"ל מסיני והיה ממובילי הפגנת המונים ב-1957 כנגד הנסיגה, אולם למרות התנגדות זו, החליטה מפלגתו להישאר בממשלה.
ביולי-אוגוסט 1957 השתתף אלון בסמינר קיץ של "בית הספר הבין-לאומי של אוניברסיטת הרווארד" בארצות הברית, בניהולו של הד"ר הנרי קיסינג'ר. בסמינר השתתפו עשרות מנהיגים צעירים מרחבי העולם.
באוקטובר 1958 הוקמה "מפלגת העבודה הערבית", שהוגדרה כמפלגת-אחות של "אחדות העבודה", אך בפועל מפלגה גרורה שלה. באופן בלתי רשמי, היה אלון אחראי למפלגה הערבית מטעם הנהגת "אחדות העבודה".
בתחילת ינואר 1959 הגיע אלון לביקור בהודו. הוא קיים בה פגישות רבות, שהחשובות שבהן היו עם ראש ממשלת הודו, ג'ווהרלל נהרו, מספר שרים בכירים, הרמטכ"ל, סגן הנשיא, יושב ראש הפרלמנט, מנהיג המפלגה הסוציאליסטית ועם אינדירה גנדי, בתו של ראש הממשלה. העיתון הקומוניסטי בהודו הציג את אלון כאחראי לליבוי המלחמה עם הערבים ב-1948 וכחבר בהנהגה הסודית של הפרוטוקולים של זקני ציון.
בשנת 1960, רק מספר חודשים לאחר שהכנסת הרביעית החלה לפעול, הודיע אלון על פרישתו ממנה ויצא שוב לאוניברסיטת אוקספורד, שם למד פילוסופיה, פוליטיקה וכלכלה.
שר העבודה (1968–1961).
בשנת 1961 שב אלון לישראל. בבחירות בנובמבר שנה זו, קיבלה מפלגת אחדות העבודה 8 מנדטים בלבד, ואלון חזר לכהן כחבר כנסת מטעם מפלגתו. הוא הצליח לחבור לאשכול ולהצטרף לממשלת בן-גוריון בתור גורם משמעותי, זאת בניגוד לרצונו של בן-גוריון ליצור קואליציה עם הליברלים. אלון מונה לשר העבודה. המשרד, שהיה מופרד ממשרד הסעד, התמקד בזכויות עובדים, כמו מתן פיצויי פיטורים, ובמציאת עבודה לעולים החדשים.
כמו כן, מונה אלון לחבר בוועדת השרים לענייני ביטחון, שהנושא המרכזי שעמד על סדר יומה היה התווית מדיניות הגרעין הישראלית, זאת לאחר חשיפת פרויקט דימונה על ידי האמריקנים בדצמבר 1960.
בדיון חשאי, התנגד יחד עם גלילי להצעת דיין ופרס להעדיף את תקצוב הכור הגרעיני על חשבון התעצמות הצבא, בטענה שהכור לא ימנע מלחמות וכי יש לחזק במקום זאת את צה"ל.
מלבד זאת, היה חבר גם ב"ועדת השרים לענייני פנים ושירותים" וב"ועדת השרים למינויים בשירות חוץ".
אלון לא השלים עם היותו חבר במפלגה קטנה יחסית, וחשב שהשפעה אמיתית על המדינה והחברה הישראלית יכולה להיעשות רק כחלק ממפלגה גדולה, שתאחד את כל מפלגות הפועלים הציוניות.
אחרי פרישת בן-גוריון מהממשלה ביוני 1963, המשיכו אלון וישראל גלילי את המאבק בתוך מפלגתם לאיחוד הסיעה עם מפא"י לקראת ריצה משותפת לכנסת לקראת בחירות 1965. מאמציהם נתקלו בהתנגדות מצד קבוצת ותיקי המפלגה בראשות יצחק טבנקין, שהציבה תנאים מוקדמים לאיחוד שכזה. מאבק זה כמעט ופילג את המפלגה, עד שבשנת 1965 אכן התבצע האיחוד (במקביל להקמת מפלגת רפ"י ופרישת אנשיה ממפא"י) והוקמה סיעת המערך (אז הוא נודע בשם "המערך הזוגי"), שהשתתפה באותה שנה בבחירות לכנסת השישית. בממשלה שהוקמה לאחריהן, בראשותו של לוי אשכול, המשיך אלון לכהן כשר העבודה. הוא גם תפקד על תקן הביטחוניסט של הממשלה, היה שותף לוועדת השרים לענייני ביטחון, וקולו בתחום המדיני-ביטחוני תפס מקום חשוב בישיבות הממשלה.
אלון כיהן כשר העבודה בשנים 1961–1968. ביולי 1965 הניח הצעת חוק בנושא ה"קואופרציה" – אחריות משותפת לתעשייה ולעבודה, אולם היא נתקלה בהתנגדות מצד תנועת המושבים ולא התקבלה. אחד מהישגיו כשר העבודה היה הסכם העבודה הקיבוצי בין ההסתדרות הכללית להתאחדות התעשיינים, שנחתם בינואר 1967. בשנת 1968 הגיש כשר העבודה את הצעת חוק בתי הדין לעבודה וזו אושרה בתחילת 1969.
מלחמת ששת הימים (1967).
ב-10 במאי 1967 הגיע אלון לביקור בברית המועצות, בראש משלחת לכנס של "ארגון הביטוח הסוציאלי העולמי" שהתקיים בלנינגרד כחלק מאירועי ציון 50 שנה ל. אלון הגדיר את הביקור כ"אחת מחוויות החיים העזות" שלו. הוא נפגש עם יהודים מקומיים, שקראו לעברו "יחי הפלמ"ח" ו"תחי מדינת ישראל", הוא ערך ביקורים בבתי הכנסת ונתכבד בפתיחת ארון הקודש. ב-18 במאי ביקר עם אשתו בטביליסי, בירת גרוזיה, בה נערכה תערוכה חקלאית, ב-20 במאי ביקרו במוסקבה, שם נפגש עם סגן שר החוץ הסובייטי, ולדימיר סמיונוב, ולמחרת ביקרו בריגה. ב-24 במאי, בעקבות מברק בהול שקיבל מהשר גלילי על רקע ההידרדרות במצב הביטחוני, שב לישראל ולמחרת ערך סיור ביחידות צה"ל בדרום הארץ יחד עם ראש הממשלה לוי אשכול והרמטכ"ל יצחק רבין.
בתקופת ההמתנה שלפני מלחמת ששת הימים, עם עליית המתיחות הביטחונית בעיקר מול מצרים, רבו גם הגישושים הפוליטיים. רבים במערכת הפוליטית סברו שראש הממשלה לוי אשכול צריך לפנות את תיק הביטחון, שאותו החזיק, לאישיות ביטחונית, שתוכל לעמוד בפרץ אם וכאשר תפרוץ מלחמה. אלון שהה באותו זמן בברית המועצות, וישראל גלילי הפעיל את השפעתו למנות אותו לתפקיד, ואף נפגש בעניין זה עם אשכול. ואולם מינויו של משה דיין, רמטכ"ל הניצחון של מלחמת סיני, נראה נכון יותר בעיני ראש המפד"ל, משה חיים שפירא, שאיים בפרישת המפד"ל אם לא תקום ממשלת אחדות הכוללת את מינויו של דיין לשר ביטחון. אליו הצטרפו סיעות רפ"י, גח"ל ול"ע, שעמדו להצטרף לקואליציה ותמכו בדיין, אשר זכה גם לתמיכה ציבורית גדולה. למרות זאת, שרי מפא"י החליטו על מינוי של אלון לשר ביטחון ושדיין ימונה כבכיר בפיקוד דרום. אולם הלחצים להקמת ממשלת ליכוד לאומי הכריעו לבסוף את הכף במזכירות מפא"י לטובת דיין, ואלון נאלץ להסיר את מועמדותו לתפקיד שבו חשק.
בימים שקדמו למלחמה, לקח חלק פעיל בפעילות ההסברה הרשמית של הממשלה לציבור.