לאחר שובה של מפלגת העבודה לשלטון בראשות אהוד ברק, בשנת 1999, מינה אותו ברק לסגן ראש הממשלה ושר התקשורת. ב-11 באוקטובר 2000 מונה לשר הבינוי והשיכון, נוסף על תפקידיו הקודמים.
ממשלתו של ברק הייתה קצרת ימים, והוא הודיע על התפטרותו ועל עריכת בחירות לראשות הממשלה בלבד, ב-6 בפברואר 2001. בבחירות אלו ניצח אריאל שרון. מגעים בין מפלגת העבודה, בראשותו הזמנית של שמעון פרס, והליכוד, הביאו להקמת ממשלת אחדות לאומית. סוכם כי מפלגת העבודה תקבל שני תיקים מרכזיים. תיק החוץ, שהובטח לשמעון פרס באופן אישי, ותיק הביטחון. בן-אליעזר התמודד במרכז המפלגה על קבלת תיק הביטחון מול חברי הכנסת מתן וילנאי ואפרים סנה, וניצח בהתמודדות. ב-7 במרץ 2001, הציג שרון את ממשלתו בפני הכנסת, ומינה את בן-אליעזר לשר הביטחון.
תקופתו כשר הביטחון הייתה תקופה של פיגועים קשים, והסלמה במלחמה שבין מדינת ישראל ובין הפלסטינים, המכונה "האינתיפאדה השנייה". שרון עלה לשלטון על רקע ציפיות לנקיטת קו תקיף. ישיבת מפלגת העבודה בממשלה, ובמיוחד ישיבתם של פרס ובן-אליעזר בתיקי מפתח, סייעו לשרון למנוע מתקפות על צעדיו בזירה הבינלאומית ומחוגי השמאל. בן אליעזר ופרס גם הצטרפו לשרון בהתנגדותו לבניית גדר הפרדה לאורך מרחב התפר בין ישראל לגדה המערבית. כלפי מפלגתו הציג עצמו שרון כמי שרוצה לנקוט בצעדים כגון "גירוש ערפאת" אך נבלם על ידי אנשי השמאל בממשלתו. ההסלמה הגיעה לשיאה בפיגוע במלון פארק ובמבצע חומת מגן שבא בעקבותיו באפריל 2002. כשר ביטחון החליט בן-אליעזר לפתוח בשורה של פעולות צבאיות, בהן נכללו כניסות ל"שטח A", שאליו ישראל מנועה מלהיכנס על פי הסכמי אוסלו. כמו כן החליט לפגוע ב-22 ביולי 2002 בסלאח שחאדה, ממנהיגי החמאס, בהפצצת ביתו בלב שכונת מגורים, באמצעות פצצה במשקל טון שהושלכה ממטוס F-16. בפעולה זו נהרגו מלבד שחאדה גם עוזרו ועוד 14 אנשים, ובהם אשתו ואחת מבנותיו, וכן נשים וילדים, ונפצעו עשרות אזרחים שהיו בקרבת מקום. הריגתו של שחאדה פתחה שרשרת סיכולים ממוקדים של מפקדי החמאס ובכיריו, צעדים שעוררו מחלוקת בקהילה הישראלית והבינלאומית.
בחודש ספטמבר 2001 התמודד על משרת יושב ראש המפלגה, אל מול אברהם בורג. הבחירות המקדימות נותרו ללא הכרעה תוך חשד כבד לזיופים, ותחת צל של פרסומים (שאחר כך הוכחו כמסולפים) על שחיתויות של מי שהיה יושב ראש הכנסת, בורג. בחודש דצמבר של אותה שנה נערך סיבוב נוסף ב-51 קלפיות שנחשדו בהיותן מזויפות. בבחירות אלו זכה בן-אליעזר ברוב הדרוש ונבחר ליושב ראש. נקבע כי המינוי הוא זמני, וכי ייערכו בחירות נוספות בשנת 2002, לקראת התמודדות בבחירות הכלליות. ישיבתה של מפלגת העבודה בממשלת האחדות לא הייתה מקובלת על יוסי ביילין וחיים רמון, שנותרו מחוץ לממשלה, והביעו את אי שביעות רצונם מתפקודה. במיוחד בלטה ביקורתו של רמון כלפי בן-אליעזר בשל אי בנייתה של גדר ההפרדה.
באוקטובר 2002, בעקבות הצעת תקציב המדינה לשנת 2003, תקציב לו התנגדה מפלגת העבודה בנימוק שהוא מנוגד לעקרונות המפלגה והבטחותיה לבוחר, הוביל בן-אליעזר לפרישת מפלגת העבודה מהקואליציה. מצבו בתוך המפלגה פנימה הלך והחמיר. בבחירות הפנימיות שהתקיימו לאחר מכן, התמודד בן-אליעזר מול רמון ועמרם מצנע, שלבסוף ניצח, אך הוביל את המפלגה לכישלון בבחירות הכלליות שהתקיימו ב-28 בינואר 2003, ולישיבה באופוזיציה.
2014-2005: שר התשתיות ופרישה מהחיים הפוליטיים.
ב-10 בינואר 2005, בעקבות אישור תוכנית ההתנתקות, הצטרפה מפלגת העבודה לקואליציה, ובן-אליעזר מונה לשר התשתיות הלאומיות. הוא פרש מתפקידו יחד עם שאר חברי סיעתו ב-23 בנובמבר 2005. בבחירות לראשות מפלגת העבודה ומועמדה לראשות הממשלה לקראת הבחירות לכנסת השבע עשרה, שנערכו ב-9 בנובמבר 2005, התמודד בן-אליעזר מול שמעון פרס ועמיר פרץ וזכה ב-15% מהקולות. עמיר פרץ ניצח בבחירות וזכה בראשות המפלגה. עם הקמת הממשלה ה-31 בראשות אהוד אולמרט, מונה בן-אליעזר בשנית לשר התשתיות.
בתחילת מרץ 2007, עמד במוקד פרשה דיפלומטית שהתעוררה בעקבות שידור סרטו התיעודי של רן אדליסט, "רוח שקד", בערוץ הראשון. בסרט הובאה עדות ולפיה גדוד שקד, בפיקודו של בן-אליעזר, הרג חיילי קומנדו מצריים שנפלו בשבי. טענות אלו, שהוכחשו על ידי יוצאי היחידה ובן-אליעזר, עוררו סערה תקשורתית במצרים.
ב-7 באפריל 2008, בעת שביקר בחמ"ל משרדו במסגרת תרגיל העורף הלאומי, אמר: "תקיפה של איראן תוביל לתגובה קשה של ישראל, שתגרום לחורבן האומה האיראנית".
בבחירות לכנסת ה-18 הוצב במקום השמיני ברשימת העבודה לכנסת ונבחר לעוד כהונה בכנסת. לאחר הקמת הממשלה ה-32 בראשות בנימין נתניהו והצטרפות מפלגת העבודה לקואליציה זו, מונה בן-אליעזר לשר התעשייה, המסחר והתעסוקה. בעקבות היעלמותה של מפלגת הגמלאים מהכנסת וכניסתו של שמעון פרס למשכן הנשיא, נעשה בן-אליעזר לזקן חברי הכנסת. ב-17 בינואר 2011 פרש אהוד ברק מהמפלגה והקים את סיעת העצמאות. בתגובה, בן אליעזר ושרי המפלגה הנוספים, יצחק הרצוג ואבישי ברוורמן, התפטרו מתפקידיהם.
ב-19 בינואר 2011, התנגדו רוב חברי הכנסת מסיעת העבודה למינויו ליושב ראש המפלגה. לקראת הבחירות לכנסת התשע עשרה הוצב בן-אליעזר במקום החמישי ברשימת העבודה. בשל היותו ותיק חברי הכנסת בכנסת זו, שימש בתפקיד יושב ראש הכנסת בפועל.
באוגוסט 2013, הצהיר בפני חברי כנסת על כוונתו להתמודד על תפקיד נשיא המדינה וביקש את תמיכתם. בפברואר 2014 החליטה סיעת מפלגת העבודה שבן-אליעזר יהיה המועמד הרשמי של המפלגה בבחירות לנשיאות ישראל. חרף זאת מספר חברי סיעה הודיעו בגלוי בתמיכתם במועמדים אחרים גם בעקבות האשמות שהועלו מצד עמיתים בעברו על התנהגות בלתי ראויה, הפרת אמונים ואף בעבירות פליליות. ב-27 במאי 2014 הכריז מועמדות לבחירות לנשיאות שיתקיימו ב-10 ביוני 2014. ארבעה ימים לפני הבחירות זימנה אותו המשטרה לחקירה באזהרה, בחשד שקיבל בניגוד לחוק כספים למימון רכישת ביתו ביפו מאיש העסקים אברהם נניקשווילי. בעקבות זאת הודיע ב-7 ביוני 2014 על פרישתו מהבחירות לנשיאות.
התדרדרות במצבו הבריאותי ומותו.
במהלך 2006 אושפז בן אליעזר פעמיים בבית החולים אסף הרופא בשל אירועי לב. במרץ 2011, אושפז בבית החולים אסף הרופא במחלקה לטיפול נמרץ במשך כ-40 יום בשל דלקת ריאות חריפה. אף שהיה חשש לחייו, החלים ושוחרר מבית-החולים. בריאיון לאילנה דיין בשנת 2014 חשף פואד שעבר אירוע שמוגדר כמוות קליני. בדצמבר 2014 אושפז בבית החולים אסף הרופא, ולאחר כשבוע ב-11 בדצמבר 2014 הודיע בן-אליעזר על פרישה מהחיים הפוליטיים, אותה נימק בהרעה במצבו הבריאותי. הוא נפטר ב-28 באוגוסט 2016, בגיל 80 ונקבר בבית העלמין בחולון
פלילים.
בדצמבר 2015 הוגש כתב אישום נגד בן-אליעזר באשמת שוחד, מרמה והפרת אמונים, עבירות מס והלבנת הון על פי כתב האישום, דרש וקיבל שוחד מאנשי עסקים בעד פעולות הקשורות בתפקידיו כשר, כמו כן מסר הצהרות הון כוזבות ליו"ר הכנסת, לא הגיש דוחות כמתחייב על פי פקודת מס הכנסה, פעל במרמה כדי להתחמק מתשלום מיסים, והלבין כספים. בפברואר 2016 החל משפטו. בן-אליעזר נפטר באוגוסט 2016, לפני שבית המשפט הספיק להכריע בעניינו.
פרקליטות המדינה הגישה תביעה כספית על סך של כ-2.7 מיליון ש"ח כנגד עיזבונו של בן אליעזר, בנימוק שהוא קיבל סכום זה כשוחד בהיותו איש ציבור ולכן על עיזבונו להשיב סכום זה למדינה. ב-2020 הסתיים המאבק על ירושת בן-אליעזר בהסכם פשרה. לפי ההסכם, המדינה הגיעה להסדר עם מנהלי העיזבון שהביא לסיומם של שלושה הליכים שניהלה המדינה נגד העיזבון - ערעור מס, הליך פלילי בבקשה לחילוט הרכוש התפוס ותובענה אזרחית שהוגשה לבית המשפט המחוזי. על פי ההסדר, העיזבון נדרש להעביר למדינה את כל סכום המזומן שנתפס בכספת של בן-אליעזר בעת הפתיחה בחקירה - סך של כ-600 אלף דולר - וכן חלק משווי זכויותיו בפנטהאוז ביפו.
באוגוסט 2019 הורשע איש העסקים אברהם נניקשוילי במתן שוחד בסך של כמיליון וחצי שקלים לבן אליעזר ובחתימה על הסכם הלוואה פיקטיבי שנועד להסוות את מתן השוחד. בית המשפט המחוזי גזר עליו עונש של 14 חודשי מאסר, שהוחמרו בבית המשפט העליון ל-21 חודשי מאסר לאחר ערעור של פרקליטות המדינה.
חיים אישיים.
הניח אישה (אשתו השנייה, דולי), חמישה ילדים ונכדים.
מקארתיזם
מקארתיזם (באנגלית: McCarthyism) הוא ההאשמה גורמת לתיוגו של המואשם, יחד עם משפחתו וחוג ידידיו, כחלק מאותה קבוצה שהוחרמה, ולפגיעה בו ובקרובים אליו – הרחקה ממקומות עבודה, ממעגלי השפעה, ופגיעה בזכויות האדם ובזכויות האזרח שלו, ובעיקר בזכויות הקשורות לחופש הביטוי. ההאשמות המובעות הן בעיקר האשמות של חוסר נאמנות, חתרנות או בגידה, והן מבוססות על שיטות חקירה בלתי הוגנות, שמועות, ראיות בלתי מספיקות ועדויות מפוקפקות. בדרך כלל האשמות אלו נועדו כדי להגביל או למנוע דעות פוליטיות שונות.