בשנת 1978 התגייס לצה"ל. את שירותו הצבאי עשה כקצין ביחידת 8200 בחיל המודיעין. לאחר שחרורו סיים לימודי משפטים באוניברסיטת ת"א, הוסמך כעו"ד והצטרף למשרד העו"ד שייסד אביו "הרצוג פוקס נאמן". בשנים לאחר מכן היה הרצוג לשותף במשרד ונטל חלק בהפיכתו לאחד ממשרדי העו"ד המובילים והרווחיים בישראל. עסק בעיקר במשפט מסחרי ועמד בראש צוות הטלקומוניקציה במשרד. בשנים 1988- 1990 שימש כמזכיר "המועצה הכלכלית החברתית", פאנל שנועד לניהול מו"מ בין ה
ממשלה, המעסיקים וארגוני העובדים.
כניסה לחיים הפוליטיים
כבר בשנת 1985 הצטרף כחבר במפלגת העבודה. בשנים לאחר מכן היה מעורב בפעילות ארגונית במפלגה, בין היתר כיועץ משפטי. בשנת 1992 היה מיוזמי הטמעת שיטת הבחירות המקדימות (פריימריס) לקביעת מועמד המפלגה לראשות הממשלה וכן שימש כיועץ מיוחד ליצחק רבין שניצח בבחירות מקדימות אלה. בשנת 1994 נבחר כחבר לשכת מפלגת העבודה.
בשנת 1999 התפטר במשרד "הרצוג פוקס נאמן" ופנה לפעילות פוליטית כעיסוק מרכזי. נמנה על חוג יועציו ומקורביו של יו"ר העבודה
אהוד ברק וסייע לו בניהול הקמפיין הבחירות לכנסת ה-15 ולראשות הממשלה. לאחר הבחירות מונה הרצוג למזכיר הממשלה ה-28 בראשות ברק (1999 – 2001). פעילותו במהלך מערכת הבחירות הפכה אותו לחשוד במסגרת פרשת "עמותות ברק" במוקדה עמד חשד לביצוע עבירות על חוק מימון מפלגות. הרצוג נחקר במשטרה ובחקירתו שמר על זכות השתיקה. בשנת 2003 החליט היועץ המשפטי לממשלה על סגירת תיק החקירה בשל היעדר ראיות.
בתום כהונת ממשלת ברק שב לעבודתו במשרד "הרצוג פוקס נאמן", כיהן כיו"ר הרשות למלחמה בסמים ובמקביל המשיך לעסוק בפעילות פוליטית. לקראת הבחירות לכנסת ה-16 שובץ במקום ה-11 ברשימת העבודה לכנסת ולאחר הבחירות הושבע כח"כ.
בינואר 2015 כאשר הצטרפה סיעת העבודה לקואליציה מונה הרצוג לשר הבינוי והשיכון בממשלתו של אריאל שרון. כעבור 10 חודשים סיים את כהונתו עם פרישת שרי העבודה מהממשלה. המשיך בכהונתו כח"כ גם בכנסת ה-17 בסיעת מפלגת העבודה. עם הצטרפות העבודה לקואליציה בראשות מפלגת "קדימה" מונה לשר התיירות בממשלה ה-31 (2009 - 2006) בראשות
אהוד אולמרט. כעבור שנה, עם הרחבת הקואליציה עבר לכהן כשר הרווחה, וכן מונה לשר האחראי לענייני תפוצות, חברה ומאבק באנטישמיות.
בבחירות המקדימות לקביעת רשימת העבודה בבחירות לכנסת ה-18 (2009) הגיע למקום הראשון. לאחר הבחירות הצטרפה העבודה לקואליציה בראשות הליכוד והרצוג מונה שוב לשר הרווחה בממשלה ה-32 בראשות בנימין נתניהו. ב-2011 פרשה סיעת העבודה מהקואליציה והרצוג התפטר מתפקידו.
בתפקידו כשר רווחה הוביל מהלך הפרטה בו שירותים חברתיים מסוימים הועברו מידי המדינה לידי עמותות במגזר השלישי שזכו בתמורה לתקצוב ממשלתי. כמו כן קידם חקיקה שאפשרה למקבלי קצבת נכות לעבוד מבלי לאבד את זכאותם לקצבה.
בשנת 2011 התמודד בבחירות לראשות מפלגת העבודה והגיע למקום השלישי (בבחירות זכתה שלי יחימוביץ'). בבחירות המקדימות רשימת העבודה בבחירות לכנסת ה-19 שוב הגיע למקום הראשון. כחבר בסיעת העבודה בכנסת ה-19 שימש הרצוג כנציג הכנסת בוועדה למינוי שופטים.
בשנת 2013 התמודד בשנית בבחירות לראשות מפלגת העבודה והפעם ניצח וגבר על יריבתו העיקרית – שלי יחימוביץ'. בתפקידו כיו"ר העבודה הוביל את המפלגה בקמפיין הבחירות לכנסת ה-20. במהלך מערכת הבחירות חבר ליו"ר מפלגת "התנועה" ציפי לבני והשניים סיכמו על התמודדות משותפת של המפלגות ברשימה אחת בשם – "המחנה הציוני". בהסכם בין המפלגות נקבע כי אם תרכיב "המחנה הציוני" את הממשלה יקיימו הרצוג ולבני רוטציה בתפקיד רה"מ.
טרום הבחירות, על פי נתוני הסקרים והערכות הפרשנים נראה היה כי ה"מחנה הציוני" אכן תרכיב את הממשלה. בבחירות זכתה הרשימה ב-24 מנדטים בלבד, מול 30 מנדטים בהם זכתה רשימת הליכוד, שהרכיבה לבסוף את הממשלה בראשות בנימין נתניהו. כישלונה של "המחנה הציוני" בבחירות הפכה את הרצוג למושא לביקורת פוליטית ותקשורתית סביב אופן ניהול הקמפיין והעצימה את הטענות נגדו כי אישיותו ודמותו כמנהיג אינן אטרקטיביות מספיק עבור ציבור הבוחרים הישראלי. בהקשר זה – מספר חודשים לאחר הבחירות הוקרן בערוץ 10 (במסגרת תוכניית "המקור") סרט דוקומנטרי בשם "הרצוג" בו תיעדה הבימאית והעיתונאית ענת גורן את התנהלותו של הרצוג במהלך מערכת הבחירות. השתתפותו בסרט כמו גם ההתנהלות שנחשפה בו העצימה את הביקורת הפוליטית נגדו.
במהלך כהונת הכנסת ה-20 ניהלו הרצוג ורה"מ נתניהו מספר סבבי מו"מ מתקדם סביב הצטרפות מפלגת "העבודה" לקואליציה, זאת למרות מספר הצהרות פומביות של הרצוג כי לא יצטרף לממשלה בראשות נתניהו. חלק מאותם סבבי מו"מ התנהלו בחשאי וללא ידיעת בכירי מפלגת העבודה וקיומם הוכחש על ידי הרצוג באופן פומבי. פרסום קיום המו"מ בדיעבד חשפה את הרצוג לביקורת עזה מצד בכירי מפלגת העבודה ובראשם שלי יחימוביץ'.
בשנת 2016 נפתחה חקירה משטרתית נגד הרצוג בחשד כי עבר על חוק מימון מפלגות במהלך הבחירות המקדימות לראשות העבודה בשנת 2013. בינואר 2017 החליט היועץ המשפטי לממשלה אביחי מנדלבליט על סגירת תיק החקירה בשל היעדר ראיות מספקות.
ביולי 2017 התמודד בבחירות לראשות מפלגת העבודה והפסיד לאבי גבאי.
ביולי 2018 נבחר לתפקיד יושב-ראש הסוכנות היהודית ובעקבות המינוי התפטר מהכנסת ופרש מהחיים הפוליטיים.
במאי 2021 הציג את מועמדותו לנשיא המדינה. בבחירות שנערכו בכנסת ביוני 2021 התמודד מול מרים פרץ וניצח לאחר שזכה ב-87 מקולות חברי הכנסת.
ביולי 2021 הושבע למשרת נשיא המדינה.
