Stefan Holenstein wuchs in Zürich auf und besuchte die Kantonsschule Zürich-Oerlikon, wo er 1981 mit der Matura Typus A abschloss. Von 1982 bis 1988 studierte er an der Universität ZürichRechtswissenschaft und arbeitete anschliessend bis 1992 als Wissenschaftlicher Assistent am Lehrstuhl für Zivilrecht und Römisches Recht der Universität Zürich. Danach wechselte er zur Universität St. Gallen, wo er wiederum als Wissenschaftlicher Assistent am Lehrstuhl für Zivilrecht und Allgemeine Rechtsgeschichte bis 1994 wirkte.[1]
Im Anschluss war Holenstein für zwei Jahre als Auditor und juristischer Sekretär am Bezirksgericht Zürich tätig. Er doktorierte 1995 mit einer rechtshistorischen Abhandlung. Danach wechselte er in die Privatwirtschaft, wo er von 1997 bis 1999 Generalsekretär beim Reisekonzern Kuoni war. Im Jahr 1999 erlangte er das Anwaltspatent des Kanton Zürichs. Von Kuoni wechselte er zur Rentenanstalt / Swiss Life, wo er bis 2000 als Rechtskonsulent tätig war. Danach arbeitete er bis 2004 als Leiter Corporate Services bei der Erb-Gruppe. Nach Abwicklung des Konkurses des Winterthurer Familienunternehmens[2] war er bis 2008 als Head Corporate Center beim Ostschweizer Bauzulieferer Arbonia, danach als stellvertretender Direktor beim Verband der Schweizer Krankenversicherer Santésuisse.[1][3] 2014 wurde er Generaldirektor des Automobil Clubs der Schweiz (ACS); das Arbeitsverhältnis endete infolge einer Verbandskrise im Juni 2016.[4][5] Der ACS und Holenstein einigten sich im Dezember 2016 einvernehmlich und aussergerichtlich.[6] Seit Mai 2017 ist er als Partner sowie Präsident des Verwaltungsrats bei einer Schweizer Interim-Management-Provider-Firma tätig.[7]
In der Schweizer Armee ist Holenstein Milizoffizier im Grad eines Obersten im Generalstab. Er wurde 1983 zum Leutnant der Artillerie, 1990 zum Hauptmann (Einheitskommandant), 1996 zum Generalstabsoffizier (als Major im Generalstab) und 1999 zum Oberstleutnant im Generalstab (Abteilungskommandant) befördert. 2005 erfolgte die Beförderung zum Generalstabsoberst; er ist seither als Stabsoffizier der Schweizer Armee eingeteilt.[1] Im Milizamt führte er die Schweizerische Offiziersgesellschaft (SOG) als Präsident von 2016 bis 2021.[8][9] Seit dem 20. November 2021 ist er Präsident vom Verband Militärischer Gesellschaften Schweiz, Nachfolger der Landeskonferenz der militärischen Dachverbände (LKMD).[10][11]