ברצועת עזה המצב הלך והסלים במהלך 2004, ויישובים ישראלים רבים – לרבות העיר שדרות שבתחומי הקו הירוק – ניצבו תחת איום מטחי רקטות הקסאם ששוגרו מהרצועה. תחת יעלון נוהלו מספר מבצעים גדולים בתחומי הרצועה (אף שגם הגדול שבהם, מבצע ימי תשובה, לא דמה בהיקפו למבצע חומת מגן), במהלכם חדרו כוחות קרקע של צה"ל אל שכונת זייתון, רפיח, בית חאנון, מחנה הפליטים ג'בליה וחאן יוניס על מנת להרוס מחרטות קסאמים, מעבדות נפץ ומנהרות הברחה. במבצעים אלה נהרגו מאות מחבלים, אך גם עשרות חיילי צה"ל (13 חיילים נהרגו ב"אסון הנגמ"שים"). ברפיח הרס צה"ל מאות בתים בניסיון לפגוע במנהרות ההברחה, אולם נחל הצלחה חלקית בלבד. ארגוני זכויות אדם מתחו ביקורת קשה על ההרס ברפיח ודחו את טענת צה"ל לפיה הדבר היה בבחינת כורח צבאי.
במקביל, נאלץ יעלון להתמודד עם קשיים שאינם מבצעיים במהותם. הדחתו את מפקד אוגדת עזה, תא"ל שמואל זכאי, בעקבות כישלונו של זה בבדיקת פוליגרף בדבר הדלפת מידע לתקשורת במבצע ימי תשובה, עוררה מחלוקת רבה בציבור ובדרג המדיני. כמו כן התמודד מול ביקורת שוטפת על שחיקת מוסר הלחימה הצה"לי בעקבות האינתיפאדה השנייה, כפי שבא לידי ביטוי, למשל, בעדויות חיילים בארגון שוברים שתיקה, בהתעללות חיילים בגופות מחבלים ובחיכוכים גוברים עם האוכלוסייה הפלסטינית במחסומים.
סביב יעלון התעוררו מספר סערות תקשורתיות, חלקן בשל דברים שאמר, חלקן בשל דברים שהוצאו מהקשרם. בין השאר צוטט (שלא במדויק) ב־3 ביולי 2003 כאומר "ניצחנו" בהתייחסו לתוצאות האינתיפאדה השנייה, שנים לפני סיומה. כוונתו המקורית התייחסה לכך שהציבור הישראלי "ניצח" בכך שרוחו לא נפלה בשל מה שכונה על ידו "מתקפת הטרור של שנת 2000". יעלון אף רמז מספר פעמים כי הוא מתנגד למעורבות היתר של שר הביטחון שאול מופז בעניינים פנים-צבאיים, וכן התעמת פעמים אחדות עם חברי ועדת החוץ והביטחון של הכנסת בראשות ח"כ יובל שטייניץ.
בתקופה שקדמה לתוכנית ההתנתקות טען בפורום סגור של ועדת החוץ והביטחון של הכנסת שנסיגה חד צדדית מרצועת עזה תהווה "רוח גבית לטרור", טענה שצוטטה מאוחר יותר בידי מתנגדי התוכנית, דבר שתרם למתח בין ראש הממשלה אריאל שרון ליעלון (בספרו "דרך ארוכה קצרה" מצדיק יעלון טענה זו, וטוען שההתנתקות היא שהביאה לניצחון החמאס והיוותה גורם למלחמת לבנון השנייה). יעלון העריך שנסיגה ישראלית חד-צדדית תתן רוח גבית לארגונים אסלאמיים רבים ברחבי העולם, והביע חשש להתפרצות גל טרור נרחב בשטחי יהודה ושומרון בעקבות התוכנית.
סיום כהונתו.
בפברואר 2005 הודיע שר הביטחון, שאול מופז, כי לא יאריך את כהונתו של יעלון בשנה נוספת וכי הלה יסיים כהונתו ביולי 2005, לפני מועד ביצוע תוכנית ההתנתקות. רבים ראו בצעד זה שיאה של המתיחות בין האישים, שסבבה סביב חילוקי דעות מקצועיים ואישיים כאחד. ראש הממשלה אריאל שרון אישר זאת באומרו כי "הרמטכ"ל לא ממשיך בגלל יחסי העבודה עם מופז". לדברי יעלון עצמו, הסיבה לכך היא שהוא התעקש להביע את דעתו על נזקי ההתנתקות בפני הממשלה.
לימים טען בספרו בתארו את אופן קבלת ההחלטה על ההתנתקות: "הוא (שרון) הלך למהלך (ההתנתקות) אשר גרם נזק אסטרטגי לישראל לא מפני שהאמין במהלך הזה, אלא מפני שביקש להציל את עצמו, כאשר החקירות הפליליות איימו עליו."
מספר שבועות לפני סיום כהונתו התבטא יעלון, בנאום שקיבל את השם "נאום הנחשים", ואמר "אני זוכר ששאלו אותי פעם מדוע אני ממשיך ללכת עם נעליים גבוהות בקריה, ועניתי להם - 'בגלל הנחשים בקריה'". רבים פרשו התבטאות זאת כתקיפה של חברי פורום מטכ"ל, אולם בריאיון בתוכניתו של יאיר לפיד ענה יעלון כי לא כיוון את דבריו ללובשי מדים, אלא לאנשי משרד הביטחון שיושבים בקריה.
כהונתו של יעלון הסתיימה ב-1 ביוני 2005. החליף אותו סגנו, האלוף דני חלוץ, שבניגוד ליעלון תמך ברעיון ההתנתקות. ב-30 במאי השתתף יעלון במפגן צניחה לציון 60 שנה לניצחון בעלות הברית במלחמת העולם השנייה, יחד עם קצינים ולוחמים מבעלות הברית, ובכך חתם 37 שנות שירות בצה"ל. בריאיון פרישה ל"הארץ" צפה יעלון: "אם אחרי ההתנתקות לא תהיה התחייבות ישראלית לעוד מהלך, תהיה התפרצות אלימה. פיגועים מכל הסוגים. ירי, מטענים, מתאבדים, מרגמות, קסאם" ו"מצבן של כפר סבא, תל אביב וירושלים יהיה כמצבה של שדרות".
לאחר פרישתו מצה"ל.
ב-2006 שהה יעלון בוושינגטון כעמית צבאי בכיר במכון וושינגטון למדיניות המזרח התיכון.
החל משנת 2006 יעלון הוא עמית בכיר במכון אדלסון למחקרים אסטרטגיים שבמרכז שלם, יו"ר המרכז לזהות ותרבות יהודית בבית מורשה בירושלים, נשיא עמותת שק"ל (שירות קהילה לאנשים עם צרכים מיוחדים) ועמית במכון לאסטרטגיה ציונית.
לאחר פרישתו מתפקידו הביע יעלון בצורה ברורה את התנגדותו לתוכנית ההתנתקות ולחזרה לגבולות 67. כבר בריאיון פרישה לארי שביט בעיתון "הארץ" (5 ביוני 2005) אמר יעלון שהפלסטינים - לרבות אבו מאזן - לא השלימו עם קיומה של מדינת ישראל, ועדיין מחפשים דרכים להשמידה. הוא הזהיר מפני גל טרור שיפרוץ לאחר ביצוע תוכנית ההתנתקות שיכלול פיגועי התאבדות וירי רקטות על ערים ישראליות, לרבות ירי קסאמים מצפון השומרון. יעלון חזה השתלטות של חמאס על רצועת עזה וקבע שפתרון שתי המדינות איננו ישים ובמקום להביא לסוף הסכסוך רק יביא לעוד פיצוץ אלים, שכן
בנאום בכנס הרצליה, ב-23 בינואר 2006, אמר יעלון כי ישראל לא יצרה הרתעה אמינה מפני הרקטות, וכי הנסיגות החד-צדדיות נתפשות כבריחה מאיום זה. כן תקף כל נסיגה המתבצעת בטרם הכירה הרשות הפלסטינית בישראל כמדינה יהודית, כאשר לדעתו המהומות בספטמבר 2000 נועדו להתחמק מהכרה כזו. כן אמר:
בנאום שנשא במכון הדסון בוושינגטון, ב-7 במרץ, התייחס יעלון לתוכנית הגרעין האיראנית ואמר שלכל צבא מערבי יש יכולת צבאית לבצע תקיפה באיראן, וברור שצריכה להיות תוכנית מוכנה לביצוע תקיפה שכזו.
גם אחרי ביצוע תוכנית ההתנתקות היה יעלון אחד ממבקריה החריפים. ביולי 2006 אמר בריאיון לארי שביט את הדברים הבאים:
מלחמת לבנון השנייה.
מלחמת לבנון השנייה התחוללה כשנה לאחר שפרש מתפקידו. במלחמה נחשפו מספר ליקויים בתפקוד צה"ל, ובפרט ועדת וינוגרד קבעה כי צה"ל לא היה מוכן כראוי למלחמה בלבנון. מפקדים רבים פרשו מתפקידם עקב תפקודם. בריאיון עמו ב-14 בספטמבר 2006 דחה יעלון את אחריותו לחוסר הצלחתו של צה"ל וטען כי בסוף תקופת כהונתו צה"ל היה מוכן למלחמה אולם הניהול המלחמתי היה כושל. הוא תקף את ראש הממשלה אהוד אולמרט על ניהול מלחמת לבנון השנייה וקרא לו להתפטר. הוא האשים אותו בכך ששלח ביומיים האחרונים למלחמה חיילים להיהרג בשביל ספין תקשורתי. עמדה שלא התקבלה על ידי ועדת וינוגרד.
הוא תקף בחריפות את מחליפו כרמטכ"ל דני חלוץ לאחר שהלה התפטר, והאשימו בהשחתה של צה"ל.
קריירה פוליטית.
ב-26 במאי 2007 אמר יעלון בתוכנית "פגוש את העיתונות" שפעולה קרקעית בעזה הכרחית, כדי לנקות אותה מטרור. כמו כן אמר שהירי הכבד לעבר שדרות ומלחמת לבנון השנייה באו בעקבות ההתנתקות.
ב-17 בנובמבר 2008, החליט יעלון להצטרף למפלגת הליכוד בראשותו של בנימין נתניהו ולהתמודד בבחירות הפנימיות לרשימת הליכוד לכנסת ה-18. הוא הודיע רשמית על הצטרפותו למחרת בנאום במצודת זאב ואמר כי "דרך הנסיגות שאנו הולכים בה היום אינה מבצרת את ביטחונה של מדינת ישראל והדרך הזו בעת הזו חייבת להיפסק". בפריימריז נבחר למקום השמיני ברשימת הליכוד לכנסת ה-18. עם כניסתה של ממשלת נתניהו השנייה לשלטון התמנה בה יעלון למשנה לראש הממשלה, שר לנושאים אסטרטגיים וחבר הקבינט המדיני-ביטחוני.
באוגוסט 2009 ביקר יעלון עם שרי ימין נוספים בהריסות חומש שפונתה בתוכנית ההתנתקות. כמו כן, השתתף בכנס של קבוצת "מנהיגות יהודית" בליכוד, בה גינה את ההתנתקות, והסביר חלק ממשנתו הפוליטית. אמר כי בישראל קיים חולי אותו כינה "הפיתרוניזם". "כשיש סכסוך, אנו מחפשים פתרון...אנחנו לא מסוגלים להכיל מציאות של בעיה ללא פתרון. הרי העולם המערבי, מצא פתרון לכל דבר, אפילו כזה שאיפשר לאדם להגיע לירח". "הפיתרוניזם, מוביל לעכשוויזם", הוא טען בכנס כי זוהי תופעה פסיכולוגית, כמו וירוס פנימי שגורם לנו להאמין שניתן להביא שלום עכשיו. הפסיכולוגיה הזאת, לדבריו, מנוצלת בצורה מניפולטיבית על ידי האליטות, מאוסלו ועד להתנתקות. דברים אלו הוצגו בחדשות ערוץ 2 כקריאה לתנועת "שלום עכשיו" וירוס, ועוררו סערה תקשורתית. עוד אמר "אנחנו התרגלנו שלערבים מותר לחיות בכל מקום: בנגב, בגליל, בשכם, בג'נין, ויש אזורים שאסורים ליהודים. זה אנחנו גרמנו". וסיכם בקשר לשאלת ההתנחלויות, ב"אשר לשאלת ההתיישבות, יהודים צריכים ויכולים להיות בכל מקום בארץ ישראל לנצח. כל התיישבות צריכה לעבור את אישור הרשויות, ומה שעולה בניגוד להחלטות לא ראוי. זה בניגוד לחוק. אדם לא יכול ללכת להתיישב באיזה מקום שהוא רוצה".
למרות התבטאויותיו אלה תמך יעלון בהחלטת הקבינט ב-25 בנובמבר 2009 להקפיא את הבנייה הפרטית החדשה באיו"ש למשך עשרה חודשים.
בעת הפעולה לעצירת המשט לעזה במאי 2010 היה יעלון ממלא מקום ראש הממשלה, עקב היעדרותו מהארץ של נתניהו. הוא הגן על ההחלטה לעצור את המשט ועל החלטת הלוחמים לפתוח באש, אך הוסיף: "במקום שבו צריך לתת צל"שים, צריך לבדוק גם את נוהל הקרב". באוקטובר 2011, משהובא לאישור הממשלה מתווה ההסכם לשחרור גלעד שליט, הצביע השר יעלון כנגד מתווה העסקה בטענה כי הדבר יהווה ניצחון לארגון החמאס ולארגוני הטרור ויסכן את ביטחונם של אזרחי ישראל.
שר הביטחון.