אחרי הבחירות ב־1996, עם עלייתו לשלטון של בנימין נתניהו, הפכתי את היציאה מלבנון לנושא עיקרי בפעילותי הפרלמנטרית, לצד פעילותי למען המשך יישום הסכם אוסלו ולהפלת ממשלת הליכוד. באותה תקופה כיהנתי כחבר בוועדת החוץ והביטחון. בדיונים שהתקיימו בנושא לא חדלתי להתווכח עם ראשי הצבא ובעיקר עם ראשי אמ"ן על הצורך הדחוף לצאת באופן חד־צדדי מלבנון.
במערכת הצבאית והפוליטית גם יחד נחשבה עמדתי לכפירה בעיקר. לא רק נתניהו ואנשי הליכוד התנגדו לעמדתי, אלא גם רוב חברי סיעת העבודה. אפילו יוסי שריד הסתייג וסבר שמוטב שהיציאה תתבצע במסגרת הסכם עם הסורים. היחיד מבין חברי הפוליטיקאים שהצטרף למאבק היה יוסי ביילין, כפי שיפורט בהמשך.
על רקע ההתנגדות הכללית בממשלה ובצבא נהגתי מדי חודש לשאת נאומים מעל דוכן הכנסת. אחד מהם נשאתי ב־9 ביולי 1997. באותו שבוע נהרג בלבנון רס"ן נדב מילוא מקיבוץ שדה אליהו. מותו היה חלק מסטטיסטיקה מחרידה: מדי שנה נהרגו בלבנון 24 חיילים בממוצע. את נאומי פתחתי באזכור מותו של רס"ן מילוא ז"ל, ובהמשך אמרתי כך:
"חובה עלינו לשאול האם המשך נוכחותנו ברצועת הביטחון בלבנון היא הדרך היחידה, ואין בלתה, שבה אפשר להגן על יישובי הצפון, או שמא יש דרכים אחרות [...]. הטענה שאי־אפשר להגן על גבול הצפון באמצעות היערכות שונה היא בלתי סבירה. זוהי טענה הנשמעת באופן חד־משמעי, בלי שהדבר נבדק, להערכתי, בדיקה משמעותית [...]. למעשה, מי שאומר את זה טוען בבירור שעדיפה הוודאות של מוות ידוע מראש של 24 חיילים בשנה [...]".
הטיעון היחיד שהעלו מתנגדי היציאה מלבנון, שראיתי בו טעם כלשהו, התבסס על החשש מפגיעה במעמדה של ישראל. לפי טיעון זה, נסיגה שלא במסגרת הסכם עלולה להתפרש בעולם הערבי ככניעה ותחליש במידה משמעותית את כושר ההרתעה של ישראל. תשובתי לכך הייתה שאפשר לפתור את הבעיה הזאת על ידי הצהרה חד־משמעית, כי כל הפרה של השקט הביטחוני אחרי יציאתנו מהשטח תוביל לתגובת־נגד עוצמתית ובלתי מידתית מצדנו.
מאז אסון המסוקים ב־1997, המאבק האזרחי למען היציאה הלך וגבר. בעקבות האסון הקימו ארבע נשים מצפון הארץ, שהיו אימהות לחיילים בלבנון, את תנועת המחאה "ארבע אימהות". התנועה הוקמה כאשר שיעור התמיכה הציבורית ביציאה חד־צדדית היה כ־20% בלבד, אך בזכות נחישותן של מייסדותיה, והודות לאסטרטגיה התקשורתית הנבונה שבה השתמשו, זכתה התנועה בסופו של דבר לתמיכת רבים בציבור הישראלי.
באותה עת קיבל עליו יוסי ביילין את המאבק למען מהלך היציאה מלבנון כמשימה מרכזית, והחל לגייס תמיכה בינלאומית לרעיון, כדי להפעיל לחץ על מקבלי ההחלטות בישראל. השינוי באווירה הציבורית הוא שהוביל את אהוד ברק, בקמפיין הבחירות שלו ב־1999, להתחייב להסיג את צה"ל מלבנון בתוך שנה מכניסתו לתפקיד ראש הממשלה. יצוין כי הצהרה זו, שכמובן בירכתי עליה, עמדה בניגוד לעמדה שהביע ברק כאשר שימש כיו"ר מפלגת העבודה וכראש האופוזיציה בתקופת ממשלת נתניהו. אזכיר כי ב־1996, כשהתחלתי בקמפיין למען היציאה מלבנון, התמיכה במהלך היציאה החד־צדדית הייתה נחלתו של מיעוט מצומצם בציבור. בישיבות סיעה של מפלגת העבודה יצא ברק נגד ביילין ונגדי: הוא האשים אותנו שאנו מספקים רוח גבית לחיזבאללה ומעודדים אותו להחריף את הטרור כלפי ישראל כדי להאיץ את נסיגתה.
למרבה השמחה, אחרי הבחירות עמד ברק בדיבורו. תא"ל במיל' עמוס גלבוע מתאר בספרו "דמדומי בוקר" כיצד בחודשים הראשונים לאחר הבחירות ברק עדיין חתר לבצע את היציאה מלבנון במסגרת הסכם שלום עם סוריה. כאשר התברר שהמשא ומתן שניהל עם הסורים נכשל כישלון חרוץ, הוא הבין שיש לפתוח בהכנות ליציאה חד־צדדית. ראשי הצבא, ובעיקר הרמטכ"ל דאז, שאול מופז, וגבי אשכנזי, שכיהן כאלוף פיקוד הצפון, התנגדו ליציאה חד־צדדית. אף על פי כן, השניים פעלו לפי הוראות הממשלה ועמדו באופן ראוי לציון במשימה שהוטלה עליהם. ב־5 במרס 2000, כתשעה חודשים אחרי הקמתה, החליטה הממשלה לסגת מרצועת הביטחון בדרום לבנון. השאלה היחידה שנשארה על הפרק הייתה מתי ואיך תתרחש היציאה. בינתיים הכין צה"ל את השטח והתארגן ליציאה מהירה.
הדחיפות בביצוע הנסיגה נבעה בעיקר מיחסינו עם צד"ל. לצד"ל לא הייתה יכולת להתמודד לבדו עם חיזבאללה, ולכן כשהתקבלה ההחלטה הסופית על היציאה, חלה הידרדרות מיידית בדרום לבנון. אנשי צד"ל, שפחדו מנקמת חיזבאללה ותומכיו, החלו להימלט מהאזור. התשתיות ששימשו אותם הלכו והתפרקו. התמוטטות צד"ל העצימה מאוד את הסכנה לחיילי צה"ל ששהו ברצועת הביטחון. לפיכך, דחיפות היציאה הלכה וגברה מדי יום.
אלוף הפיקוד, גבי אשכנזי, הבין היטב את חומרת המצב. למרות התנגדותו העקרונית לעצם היציאה, הוא ידע כי משעה שהתקבלה ההחלטה, יש לממשה בהקדם. אשכנזי רצה לא רק לשמור על חיי חייליו, אלא גם למנוע מצב שבו תיתפס נסיגתנו מרצועת הביטחון כבריחה מאולצת. אולם כאשר גברה הבהילות ביציאה, אהוד ברק, ולא הדרג הצבאי, נהפך לגורם המעכב. כפי שעמוס גלבוע מתאר בספרו, מתחילת מאי 2000 התגלעה מחלוקת בין ברק לאנשי פיקוד הצפון בראשותו של אשכנזי. פיקוד הצפון רצה לצאת מיידית מלבנון, ואילו ברק העדיף לדחות את הנסיגה עד אישורה באו"ם. הוא רצה להמתין להכרזה שהנסיגה מתבצעת על פי החלטה 425 של מועצת הביטחון של האו"ם, שהתקבלה במרס 1978 בעקבות כניסת ישראל ללבנון במבצע ליטני. באותה החלטה נקבע כי על ישראל להסיג את כוחותיה מלבנון עד לקו הגבול הבין־לאומי.
ברק מיאן להכיר במה שאשכנזי, שהכיר מקרוב את הנסיבות בשטח, ידע בבירור: לנוכח המצב הדליק בדרום לבנון, שהידרדר מרגע לרגע, המתנה לאישורו של האו"ם הייתה בבחינת מותרות שלא יכולנו להרשות לעצמנו. במהלך התכנסות של צוות שרים שבה השתתפתי ושנערכה במוצאי שבת, 20 במאי 2000, אשכנזי סקר את המצב בדרום לבנון וצייר תמונה קשה ביותר. הוא הסביר כי צד"ל, בן בריתנו באזור, עומד לפני התפוררות, וכי ארגון חיזבאללה יודע זאת היטב ומתכונן להשתלט על האזור.
תיאוריו הקודרים של אשכנזי החרידו אותי. בראש ובראשונה חששתי מהמחיר הכבד שנשלם בנפש אם נמשיך לעכב את יציאתנו מלבנון, אך כמו אשכנזי, גם אני חששתי מן המכה המורלית והתדמיתית הקשה שנספוג אם ניאלץ לברוח משם מתוך אילוץ ולא מתוך בחירה. ואולם להפתעתי התברר שברק אינו מתרגש מדבריו של אשכנזי, והוא ממשיך להתעקש על 6 ביולי, התאריך המדויק שעליו הכריז בעבר כמועד האחרון ליציאה. הוא ביקש לנצל עד תום את הארכָּה בת השנה שלקח לעצמו לצורך היציאה מלבנון במסגרת הצהרותיו במערכת הבחירות. ארכָּה זו הייתה מאפשרת לכאורה לתאם את הנסיגה עם האו"ם, אבל בנסיבות הבוערות שנוצרו ברצועת הביטחון לא היה בדחייה הזאת שום היגיון.
לא השלמתי עם התעקשותו המופרכת של ברק. נטלתי את רשות הדיבור והפניתי את דברי אל ראש הממשלה. עמדתי על כך שתתקבל החלטה על יציאה מיידית מלבנון, אך לדאבוני צוות השרים לא החליט דבר.
עמוס גלבוע מספק בספרו עדויות לעימות נוסף שאירע בין אשכנזי לברק, כעבור יומיים, בנוגע למועד היציאה המדויק. בבוקר 22 במאי ערך ברק כינוס באזור הצפון עם ראשי הצבא וקהילת המודיעין, שמטרתו הייתה לדון באפשרות חיסולו של עימאד מורנייה, "רמטכ"ל חיזבאללה". גלבוע ממשיך ומספר בספרו שאשכנזי רשם את תקציר המפגש. לפי התקציר קטע אשכנזי את הדיון על מורנייה ואמר לברק: "ראש הממשלה, מוכרחים לצאת! עדיף לצאת עכשיו, חיזבאללה לא מוכן לזה, נפתיע את כולם, לא יהיו הרבה נפגעים. עכשיו יש בידינו כל היתרונות, אבל בתוך כמה ימים נאבד אותם ונישאר עם כל המגרעות". בתשובה, לפי התקציר, אמר ברק לאשכנזי: "אני חייב שיהיה לי זמן כדי למצות את התהליך של 425, אני זקוק לעוד חודש". על פי תיאורו של גלבוע, כל הנוכחים האחרים בדיון תמכו בעמדתו של אשכנזי, אבל גם בכך לא היה די לברק, שעמד על דעתו.
בכינוס נוסף של צוות שרים שהתקיים בהמשך אותו יום, ברק דבק בעמדתו. בשלב זה, צד"ל כבר היה על סף התפוררות סופית, ולבנונים רבים ביקשו להימלט לישראל, בהם אנשי צד"ל. הצעתי לראש הממשלה שישראל תאפשר כניסה מיידית לכל הנמלטים המתדפקים על שעריה, בלי לבצע בידוק ביטחוני בשערי הגדר, באותה ישיבה אמרתי כך:
"אני מבקש לצאת מלבנון הכי מהר שאפשר [...] עכשיו ברור שאין מדובר במצב שאנחנו יוצאים, והאו"ם נכנס במקביל והכול יהיה בשלווה. יש קו אחד, יש קו נסיגה, האו"ם קבע אותו. יודעים בדיוק לאיזה גבול אנחנו חוזרים כדי למלא את החלטה 425 [...] לאחר שנצא - פגיעה בקריית שמונה או בכל מקום אחר בגבול הצפון תיחשב כפגיעה בתל אביב. זו המשמעות". למחרת, ב־23 במאי, שוב התכנס צוות שרים לדון במועד היציאה. אשכנזי המודאג, שישב בסמוך אלי והבין שברור לי שהיציאה אינה סובלת דיחוי, לחש על אוזני: "חיים, תציע לצאת הלילה, כי הכול יכול להתמוטט מחר או מחרתיים".
אשכנזי התכוון לכך שכוחות צד"ל עלולים להתמוטט סופית כל רגע. ואכן, בדברים שנשאתי בישיבה שוב הפצרתי בראש הממשלה להקדים את היציאה ככל האפשר. גם מתן וילנאי, שכיהן כשר ונכח בישיבה, תמך בגישה הזו. אף על פי כן, ברק עדיין התקשה לוותר על הפרדיגמה שדבק בה, ולפיה מהלך היציאה מלבנון צריך להיעשות בתיאום עם האו"ם. בסופו של דבר, בתוך שעות ספורות, הבין ברק שכָּלו כל הקִּצין, ואין ברירה אלא להורות על יציאה מיידית, שכן צד"ל התמוטט כליל וחדל להתקיים. יציאתנו מרצועת הביטחון נקבעה ל־24 במאי. בנסיבות שנוצרו, עם היעלמות צד"ל מהתמונה ולאחר שכל הגשרים כבר נשרפו, התפרשה יציאתנו כבריחה במקום כהחלטה יזומה, והייתה לכך משמעות קשה.
ב־26 במאי 2000 נשא מזכ"ל חיזבאללה, חסן נסראללה, את "נאום קורי העכביש" שלו, שבו הכריז שלמרות עוצמת הכוח הגרעיני והאווירי שלה, "ישראל חלשה יותר מקורי עכביש".
ההחלטה על היציאה מלבנון הייתה נכונה וחיונית, אך בשל התמהמהותו של ברק שילמנו מחיר מיותר מבחינת מעמדנו מול חיזבאללה, שהציג את המהלך כניצחון שלו וכתבוסה של ישראל. ראוי לציין את התנהלותו המופתית של גבי אשכנזי, שלמרות שהתנגד ליציאה חד־צדדית, מעת שנתקבלה ההחלטה ארגן את הצבא ואת צד"ל בצורה יוצאת דופן לקראת הנסיגה. ההישג המשמעותי ביותר של אשכנזי היה שלמרות הכאוס ברצועת הביטחון ערב הנסיגה אף חייל של צה"ל לא נהרג ולא נפצע וכל חיילינו שבו לגבולנו בשלום. כמו כן, נמנע טבח באנשי צד"ל על ידי חיזבאללה.
למרות ביקורתי על אהוד ברק לגבי אופן ביצוע הנסיגה, אין ספק שהחלטתו האסטרטגית לבצע את הנסיגה החד־צדדית מלבנון הייתה אמיצה וראויה לכל שבח, וייתכן שאלמלא החלטתו היינו מתבוססים בבוץ הלבנוני עד עצם היום הזה.