כניסתו המחודשת של אהוד ברק אל הפוליטיקה הישראלית כללה גם התקפה אישית קשה על ראש הממשלה, בנימין נתניהו. ברק אמר כי "אלו ימים חשוכים שלא ידענו כמותם. נתניהו ויו"ר הכנסת עושים שימוש בכלים ממלכתיים לכאורה, שבועות בודדות אחרי שפיזרו את הכנסת אחרי שנתניהו נכשל. אנחנו לא עיוורים - מערכת הבחירות האחרונה הוקדמה בשביל לשבש את מהלכי המשפט של נתניהו, השאלה איננה אם את מקומו של נתניהו יתפסו גדעון סער או ישראל כץ, אלא למי יש את הניסיון לשנות את המסלול של מדינת ישראל. נתניהו הגיע לסוף דרכו. יודעים זאת גם טובי מקורביו וגם חבריו לסיעה ולממשלה, רובם אחוזי שיתוק ופחד".
דברים אלו הם פרק חדש ביחסים המורכבים בין השניים שחוזרים אחורה עוד לשנות השבעים של המאה הקודמת, ולקשר שבין אהוד ברק לנתניהו הצעיר כקצין בסיירת מטכ"ל, וכן לקשר גם בין יוני נתניהו ז"ל, בנימין נתניהו ואהוד ברק. על התקופה בסיירת אמר פעם ברק כי נתניהו היה קצין טוב וכי יוני היה חברו האישי של ברק. בהמשך, בעת שנתניהו פרש מהצבא, למד בארה"ב ואף כיהן כשגריר באו"ם, לא נוצר קשר עמוק בין השניים.
המציאות הזו השתנתה אחרי 1996, אז ניצח בנימין נתניהו את שמעון פרס, מנהיג מפלגת העבודה, בבחירות. אהוד ברק ירש את תפקידו והתמודד מול נתניהו בבחירות 1999, ואף ניצח את ראש הממשלה המכהן. את ניצחונו על בנימין נתניהו הגדיר אז ברק כ"שחר של יום חדש". אולם השחר הזה היה קצר, ומהר מאד איבד ברק את השלטון ויצא לעסקים פרטיים, כמו נתניהו עצמו שפרש מן הפוליטיקה לאחר ההפסד לברק.
הקשר המחודש בין השניים החל בשנת 2009, בממשלתו הראשונה של נתניהו לאחר ניצחונו בבחירות. אז הפכו נתניהו וברק למובילי התגובות נגד נאום קהיר של הנשיא ברק אובמה, וברק הגן בוושינגטון על מדיניותו של נתניהו לאורך כל התקופה. למעשה, באותה תקופה התחממו מאוד היחסים בין השניים, ששוחחו על בסיס יומי, נפגשו רבות וחידשו את הקשר שהחל בסיירת מטכ"ל. קשר זה גרר ביקורת קשה על ברק מצד גורמים משמאל, שלפי ראייתם הוא הגן על נתניהו מהתקפות של אובמה. עם זאת, ברק הודיע ב-2012 כי לא יתמודד שוב לכנסת, ולמעשה פרש אז מהחיים הפוליטיים, אם כי לא מפעילות ציבורית.
נתניהו וברק בישיבת ממשלה // צילום: אריאל חרמוני
עם זאת, בשנים האחרונות החל ברק להתבטא בחריפות גדולה מאוד כנגד ראש הממשלה. לדוגמה, אחרי כישלון המבצע ברצועת עזה בה נהרג הקצין מ', כתב ברק: "הלב עם משפחתו הגדולה של מ׳ ועם יחידתו -שאיבדו בן משפחה, לוחם ומפקד יוצא דופן. הראש תוהה על שיקול הדעת של נתניהו והבטן מתכווצת מהמחשבה, שבלילה שבו יודעים מראש שעומד לצאת מבצע כזה לדרך, עומדת בראש המדינה, בהחלטה אישית של ראש הממשלה, מירי רגב, בעודו מתחמק בפריז משאלות על ׳שוחד כלי השיט׳".
לפני כן, כשנאם על מצב האומה ב-2018, אמר ברק כי "בשנים האחרונות, תחת שלטון נתניהו וגורמים קיצוניים, חל שיבוש עמוק בחזון. במקום להתמקד בעצמנו, בגיבוש אחדותנו הפנימית וכוחנו ובדחף היצירה של האזרחים, מצמיחים שלטון נתניהו והקיצונים חזון אחר שבמוקדו: 'הם', ולא 'אנחנו'. פחד עמוק מ'זרים', 'גויים' ו'עמלקים' מבחוץ, ומ'בוגדים' ו'משתפי פעולה' עם אויבינו מבפנים. שיסוי והסתה של ישראלים זה בזה, וזריעת שנאת זרים, מוחלשים וקבוצות מיעוט. שנאת אחים ופרימת הרקמה החברתית, לקול תשואותיו של ה'בייס' המיתולוגי".
בשנת 2013, לקראת פרישתו מהפוליטיקה, גיבה ברק את נתניהו וממשלתו ולא ראה בעמדות מדיניות סיבה לכישלון הממשלה, אלא דווקא במחאה החברתית. אז אמר ברק כי "מאות אלפי האנשים שיצאו לרחובות בישראל במהלך המחאה החברתית וזכו להתעלמות מהממשלה, שאני הייתי חלק ממנה, באו לקלפיות. הם בעצם אמרו לנו 'אנחנו רוצים את מנת חלקנו במה שקורה בישראל'. זאת אמירה לממשלה שיש גבול למה שהציבור יכול לספוג".
מערכת יחסים הפכפכה // צילום: אריאל חרמוני
לפני כן תמך ברק בנתניהו, וכשראש המוסד לשעבר מאיר דגן תקף את השניים על רצון לפעול באיראן, אמר: "כאשר באופן חסר תקדים, ראש מוסד מביא עיתונאים למטה המוסד ומתדרך אותם נגד ראש הממשלה... אני חושב שההתנהגות הזו חמורה מאוד. הייתי מצפה ממנו לנהוג בשכל וללא מניפולציות, אני מקווה שזה לא נגוע בשיקולים זרים. התיאור כאילו יושבים שני אנשים, אני וראש הממשלה, בחדר סגור ומובילים מהלך של תקיפה - זה הזוי. ראוי שהשיח יתנהל בצורה אחראית ורצינית, שיהיה ברור שנתניהו וברק זה לא בובליל ובשבקין. אנו מביטים על המצב יום אחרי יום, באחריות, אין פה שום סכנה, אנחנו לא פועלים לבד ובכל מקרה צריך את אישור הממשלה לכל דבר".
מנגד גם נתניהו לעג לברק עם השנים, לדוגמה אחרי שברק הזהיר ב2017 מצונאמי מדיני נגד ישראל העלה נתניהו סרטון לעמוד הפייסבוק שלו בו היא חיקה בלגלוג את המבטא של ברק ואמר: "ישראל היא מדינה מחוזרת, וזה נמשך ממדינה למדינה ומיבשת ליבשת". איפה הבידוד? איפה הצונאמי?" אמר נתניהו כשהוא אומר טסונאמי, כדרך הגייתו של יריבו. מנגד אמר ברק בראיון לגלי צה"ל ב-2018: "הוא לא יותר קוסם מאשר הקוסם שאתה מביא ליום ההולדת של הבן שלך. אין לו כוחות עליונים, הוא רק מאחז עיניים. אם אני ניצחתי אותו ב-99, אפשר לנצח אותו גם היום".