כשיצא בן-גוריון לחופשה של שלשה חודשים ב-19 ביולי 1953, הוא מינה את לבון כממלא מקומו במשרד הביטחון. לאחר שהודיע על פרישתו לשדה בוקר ב-7 בדצמבר 1953 מינה את לבון כשר ביטחון במקומו ומשה שרת מונה כראש ממשלה. יום לפני כן מינה את שמעון פרס למנכ"ל משרד הביטחון ואת משה דיין לרמטכ"ל. ההרכב הפרסונלי הזה היה הגורם העיקרי למתחים ולסכסוכים שליוו את תקופת כהונתו של לבון כשר הביטחון.
בתקופה שקדמה לקום המדינה היה לבון רחוק מנושאי הביטחון ביישוב. הוא החזיק בעמדות מתונות בנושאים המדיניים והביטחוניים ונמנה עם האגף המתון במפא"י. הוא הסתייג מפעולות אלימות כנגד הבריטים והתנגד למעשי נקמה אלימים, הכוללים פגיעה בחפים מפשע, בתגובה לטרור הערבי. פעילותו במשרד הביטחון החלה בתקופה שהתאפיינה במתח ביטחוני רב. פלסטינים שחיו במחנות פליטים ברצועת עזה ובירדן ניסו עם תום מלחמת העצמאות להסתנן אל מעבר לגבול כדי לחזור לכפריהם, לקצור את שדותיהם ולאסוף את היבול. בהמשך החלו המסתננים להתארגן בקבוצות. מקצתן של הקבוצות גויסו לשם פעולות מודיעין בישראל ואחרות ביצעו מעשי שוד, חבלה ורצח. ישראל הגיבה בפעולות תגמול שאותן הובילו בן-גוריון ודיין, בעוד ששרת הסתייג מהן כשר החוץ ואחר כך כראש הממשלה וסבר שעל ישראל להגיב במישור המדיני על ידי תלונות לוועדת שביתת הנשק של האו"ם. לבון סבר שהתלונות הללו אינן אפקטיביות, ועל מעשי טרור יש להגיב בפעולות תגמול צבאיות. לבון, על אף עברו המתון, תמך בפעולות התגמול, אם כי הזהיר מפני ריבוי מקרים של פעולות שלא קיבלו את אישור הדרג המדיני ומפני פעולות הפוגעות באוכלוסייה חפה מפשע.
דוגמה מובהקת לחילוקי הדעות בין לבון ושרת היא פרשת "בת גלים". המצרים חסמו את תעלת סואץ בפני אוניות ישראליות, בניגוד לדרישת המעצמות. ביוזמת שרת נשלחה האנייה "בת גלים" כדי להעמיד את המצרים במבחן. המצרים עצרו את האנייה ושבו את צוותה. האו"ם והמעצמות מחו בקול רפה, אך לא נקפו אצבע, בדיוק כפי שלבון חזה. חילוקי הדעות הללו זכו לביטוי פומבי כאשר שרת הציג בכנסת את השאלה האם מדינת ישראל חפצה להיות "מדינה של חוק או של שוד"? בדיון אחר בכנסת התייחס לבון לשאלה זו באומרו:"מדינת ישראל, כמו כל מדינה, חיה על פי שני חוקים – ואין סתירה בין שני החוקים האלה. החוק האחד הוא החוק הבינלאומי, ומדינת ישראל רואה עצמה מחויבת לפעול על פי החוק הזה. אבל היא חיה גם על פי חוק שני, שעל פיו חיות גם יתר המדינות, והוא החוק הטבעי של ההגנה העצמית".עם זאת לבון נכשל בדיווח לקוי לראש הממשלה הממונה עליו. פעמים רבות בוצעו פעולות צבאיות בניגוד להוראות הדרג המדיני או תוך חריגה מהן. לבון נאבק בראשי הצבא על מנת לאכוף משמעת, אך כלפי חוץ העניק גיבוי לקצונה הבכירה וכך נוצר הרושם שלבון מנהל מדיניות עצמאית בניגוד לדעתו של ראש הממשלה. כתוצאה מכך הורעו מאוד היחסים בין שרת ולבון.
היחסים בין לבון לבין דיין לא היו תקינים מלכתחילה, ובמהלך כהונתו של דיין כרמטכ"ל תחת שר הביטחון לבון, הורעו היחסים אף יותר. לבון היה איש דור הביניים במפא"י, ויריבו הפוליטי של דיין. ברוח הימים ההם היה דיין חבר מרכז מפא"י והתפטר ממנו רק משהתמנה לרמטכ"ל. לבון ראה את עצמו כיורשו של בן-גוריון, ואת מינויו לשר ביטחון ראה כאישור למעמדו זה. ראייה זו הכניסה אותו למסלול התנגשות עם חבורת הצעירים שטיפח בן-גוריון, ובראשם דיין ושמעון פרס ששימש כמנכ"ל משרד הביטחון. על אף ששני האישים, דיין ולבון, החזיקו בראייה ביטחונית דומה, החלו עד מהרה סכסוכים ביניהם. המאבק על הסמכויות בין שר הביטחון לבין הרמטכ"ל הביא לחוסר בהירות באשר לשאלת הקשר הישיר בין קצינים בכירים ובין שר הביטחון. כאשר נודע לדיין, באמצע 1954 כי מפקד חיל האוויר, דן טולקובסקי, נועד ישירות עם לבון, הגיש את התפטרותו, אך שוכנע על ידי דוד בן-גוריון לחזור בו.
לחילוקי דעות אלו היו גורמים נוספים, שהתבטאו אף בדברים עקרוניים, כגון דרישתו של דיין לרכוש מן הצרפתים טנקים מסוג AMX-13, עליה הטיל לבון וטו. דיין ופרס ראו חשיבות עליונה ביצירת ברית עם ממשלת צרפת, תוך תמיכה במדיניותה הקולוניאליסטית באלג'יר. דיין אף הציע לצרפתים שיתוף פעולה צבאי באלג'יר. לבון, שהבין שהעידן הקולוניאליסטי הגיע לידי סיום, ראה בצרפת משענת קנה רצוץ ושאף לחיזוק הקשרים עם ארצות הברית. תפיסתו של לבון מומשה כעשר שנים מאוחר יותר בימיו של לוי אשכול כשר הביטחון.
לבון נתקל בקושי לכפות את מרותו כשר גם על המנכ"ל פרס. בניגוד לבן-גוריון שנהג לפקוד את משרד הביטחון רק פעם בשבוע היה לבון שר ביטחון במשרה מלאה, פעיל ויורד לפרטים. הוא חלק על טענת פרס שמערכת הביטחון יעילה וראה הזדמנויות לחיסכון גם במערכת הביטחון. הוא קיצץ בצבא הקבע מבלי לפגוע במצבת הכוח הלוחם, ובכך אפשר הצטיידות של הצבא באמצעי לחימה נוספים. בשנת כהונתו כשר ביטחון הוגדלה מצבת החטיבות הלוחמות של צה"ל. יחידה 101 פורקה והשתלבה בחטיבת הצנחנים.
עסק הביש.
לבון עמד על זכותו כשר ביטחון להמשיך בפגישות עם בכירי צה"ל, וביניהם ראש אמ"ן, אל"ם בנימין גיבלי. לימים תהיה לעניין חשיבות מכרעת בשאלה "מי נתן ההוראה" לגיבלי להפעיל רשת של מרגלים יהודים במצרים, ולהורות להם לחבל במתקנים בריטים על מנת למנוע את הסתלקותה של בריטניה מאזור תעלת סואץ. בעת שניתנה ההוראה לגיבלי, היה דיין בביקור בארצות הברית, ולבון טען כי לא הוא שנתן את ההוראה. לימים תהיה לפרשיה זו, שנודעה בכינוי "העסק הביש", חשיבות מכרעת בהיסטוריה הפוליטית של מדינת ישראל. על פי יומניו של משה שרת, לבון רצה ליזום פעולות פרובוקציה נוספת במדינות ערב, בין השאר להפציץ בירות שונות במזרח התיכון, בהן בגדאד, ולפגוע בקונסוליה הבריטית כדי לסכסך בין הממלכה המאוחדת וירדן.
ב-8 בדצמבר 1954 הודיעה מצרים כי חשפה רשת ריגול ישראלית. העצורים, צעירים יהודים אזרחי מצרים, נשפטו לתקופות מאסר ארוכות, ושנים מהם אף נתלו על חלקם ברשת. פעולות הרשת נחשפו עוד ביולי 1954. על אף שישראל הכחישה את חלקה ברשת, התברר כי גורמים בצה"ל הורו לצעירים לפגוע באתרים בעלי קשר לבריטניה ולארצות הברית, על מנת להבאיש את ריחה של מצרים בעיני מדינות המערב.
ניסיון ראשון לברר מי אחראי לתסבוכת שנוצרה נעשה על ידי שרת, שמינה לשם כך ועדת שניים: נשיא בית המשפט העליון, יצחק אולשן, והרמטכ"ל לשעבר, יעקב דורי. הוועדה לא הצליחה לרדת לשורש העניין, וכתבה: "לא שוכנענו למעלה מכל ספק המתקבל על הדעת כי ראש אמ"ן לא קיבל את ההוראה משר הביטחון פנחס לבון. עם זאת, איננו בטוחים שלבון נתן את ההוראה המיוחסת לו". בעקבות פעילות הוועדה התפטר לבון מתפקידו בפברואר 1955, אף שטען כי לא נתן את ההוראה.
התעוררותה מחדש של הפרשה.
בשנת 1960 התעוררה מחדש "הפרשה". דוד בן-גוריון כותב בספרו "דברים כהוויתם": . בן-גוריון מוסיף כי ביקש גם הקמת ועדת חקירה בעניין "האדם השלישי", שהיה קשור ב"עסק הביש", "ועדת כהן", שהוקמה בעת שהותו של לבון בחו"ל. לבון, על ידי מזכירו, ביקש מבן-גוריון את ביטולה. בשובו לישראל, נפגש לבון עם בן-גוריון ב-26 בספטמבר 1960 ודרש את טיהור שמו מן האחריות ל"עסק הביש". בן-גוריון סירב ואמר לו: . לבון פירש זאת כהתחמקות ותקף בחריפות את שמעון פרס, שהיה מנכ"ל משרד הביטחון בתקופת "העסק הביש", ואת מי שהוזכר רק בכינוי "הקצין הבכיר" - בנימין גיבלי, שעמד בראש אגף המודיעין של צה"ל. גיבלי טען שקיבל הוראה בעל פה משר הביטחון, לבון.
ועדת בירור שמינה הרמטכ"ל, בראשות השופט חיים כהן, לא גילתה הוכחות לזיוף המכתב של גיבלי, אך קבעה כי נעלמו מסמכים והייתה הדחה לעדות שקר וכך חיזקה בממצאיה את טענותיו של לבון.
ב-1958 נעצר ונשפט אברי אלעד מי שכונה "האדם השלישי", מפעיל הרשת במצרים ואחד מהעדים נגד לבון בוועדת אולשן-דורי, בגין מגע עם סוכן זר, והגילוי כי הוא נחשד כסוכן כפול מצרי. בעקבות זאת החליטה הממשלה למנות לבירור נוסף ועדה שהורכבה משבעה שרי ממשלה, בראשותו של שר המשפטים, פנחס רוזן. ב-25 בדצמבר 1960 הגישה "ועדת השבעה" את מסקנותיה, שבהן נקבע פה-אחד שלבון לא נתן את ההוראה, ואף לא ידע על הפעולה. בעקבות מסקנות אלה התפטר בנימין גיבלי מצה"ל. לימים התברר כי עדויות קציני אמ"ן בפני ועדת אולשן-דורי היו מתואמות, ומסמך שהוצג בפניה זויף על ידי דליה כרמל, מזכירתו של בנימין גיבלי.
בן-גוריון, שלא הסכים למתן זיכוי לפוליטיקאי על ידי ועדה של פוליטיקאים (גם אם כולם שרים) שאינה "ועדת חקירה משפטית", דרש (מסיבות אחרות, לדבריו) להדיח את לבון מהזירה הפוליטית. בציבור נוצר הרושם כאילו בן-גוריון רואה בלבון אויב אישי, ורודף אותו על לא עוול בכפו. מרכז מפא"י, שנאלץ להכריע בסכסוך זה, נכנע ללחצו של בן-גוריון, ובתחילת 1961 הדיח את לבון מתפקיד מזכ"ל ההסתדרות, ומחק אותו מרשימת מועמדי המפלגה לכנסת.
מן היסוד.