Nach einer Cello- und Gesangsausbildung sowie vielfachen Tätigkeiten u. a. an der Oper in seiner Heimatstadt Oslo, studierte Herheim Musiktheaterregie bei Götz Friedrich an der Hochschule für Musik und Theater in Hamburg.
Von der frühbarocken Oper bis hin zum zeitgenössischen Musiktheater spannt sich das Repertoire, das Herheim an zahlreichen Opernbühnen und renommierten Festspielen in Zusammenarbeit mit Dirigenten wie Daniel Barenboim, Adam Fischer, Daniele Gatti, Mariss Jansons, Andris Nelsons, Antonio Pappano, Donald Runnicles und Simon Rattle inszenierte.
Er ist Träger von etlichen internationalen Preisen und wurde bei der Kritikerumfrage der Zeitschrift Opernwelt dreimal zum „Regisseur des Jahres“ gewählt.
Regelmäßig unterrichtet Herheim an europäischen Hochschulen und ist als Juror bei internationalen Wettbewerben tätig. Seit 2018 ist er Professor an der Norwegischen Opernakademie.
Bei der diesjährigen Verleihung der Opera Awards im Teatro Real Madrid wurde Stefan Herheim mit dem Preis in der Kategorie Director/Regisseur ausgezeichnet.
Zu seinen Inszenierungen zählen u. a. THEODORA (MusikTheater an der Wien, 2023), AMAHL UND DIE NÄCHTLICHEN BESUCHER (MusikTheater an der Wien, 2022), DAS SCHLAUE FÜCHSLEIN (MusikTheater an der Wien, 2022), PETER GRIMES (Bayerische Staatsoper, 2022), DER RING DES NIBELUNGEN (Deutsche Oper Berlin, 2020 – 2021), PELLÉAS ET MÉLISANDE (Glyndebourne Festival 2018), BLAUBART (Komische Oper Berlin, 2018), WOZZECK (Deutsche Oper am Rhein, 2017), LA CENERENTOLA (Norwegische Nationaloper, 2017), PIQUE DAME (Niederländische Nationaloper, 2016), LE NOZZE DI FIGARO (Hamburgische Staatsoper, 2015), LES CONTES D’HOFFMANN (Bregenzer Festspiele 2015), LES VÊPRES SICILIENNES (Royal Opera House Covent Garden, 2013), DIE MEISTERSINGER VON NÜRNBERG (Salzburger Festspiele 2013), MANON LESCAUT (Oper Graz, 2012), XERXES (Komische Oper Berlin, 2012), LA BOHÈME (Norwegische Nationaloper, 2012), SALOME (Salzburger Osterfestspiele 2011), EUGEN ONEGIN (Niederländische Nationaloper, 2011), LULU (Königliche Oper Kopenhagen, 2010), TANNHÄUSER (Norwegische Nationaloper, 2010), DER ROSENKAVALIER (Staatsoper Stuttgart, 2009), LOHENGRIN (Staatsoper Berlin, 2009), RUSALKA (Theâtre de la Monnaie Bruxelles, 2008), PARSIFAL (Bayreuther Festspiele 2008), DON GIOVANNI (Aalto-Theater Essen, 2007), CARMEN (Oper Graz, 2006), DAS RHEINGOLD (Lettische Nationaloper, 2006), LA FORZA DEL DESTINO (Staatsoper Berlin, 2005), GIULIO CESARE (Norwegische Nationaloper, 2005), MADAMA BUTTERFLY (Volksoper Wien, 2004), DON CARLO (Landestheater Linz, 2003), DIE ENTFÜHRUNG AUS DEM SERAIL (Salzburger Festspiele 2003), I PURITANI (Aalto-Theater Essen, 2002), MARLOWE – DER JUDE VON MALTA (Münchner Biennale, 2002), COSI FAN TUTTE (Folkoperan Stockholm, 2002), TANNHÄUSER (Landestheater Linz, 2001), FALSTAFF (Oldenburgisches Staatstheater, 2000), ÜBER FRAUEN - ÜBER GRENZEN (Münchner Biennale, 2000), COSI FAN TUTTE (Vanemuine Theater Estland, 2000) sowie DIE ZAUBERFLÖTE (Oldenburgisches Staatstheater, 1999).