Dès l'âge de 17 ans, Stéphane Guillaume entre dans le monde du jazz en se produisant aux côtés de Jean Bonal, de Jacques Vidal, de Ted Hawke... En même temps lui est décerné un 1er prix du conservatoire de paris en saxophone classique. Son passage dans la classe de Jazz de François Jeanneau lui permet de rencontrer et de jouer avec des musiciens tels que Randy Weston, George Russell, Dave Liebman...
En septembre 1994, Laurent Cugny l'engage dans l'Orchestre National de Jazz avec lequel il enregistre trois disques. Cet orchestre lui donne l'occasion de rencontrer Lucky Peterson, Tommy Smith, Maria Schneider, ou encore Enrico Rava…
En 1996, il réalise l'album « Miage », première tentative discographique sous son nom, mais c'est évidemment son activité de sideman qui prédomine. Il va se produire dans diverses aventures musicales : le quatuor « Y'aka Sax » (1996-2002), le quintet de David Patrois (1997-1999), le « Big-Band Lumière » de Laurent Cugny (1997-2001), le « Jazz Ensemble » de Patrice Caratini (1997-2003), le quintet de Stéphane Huchard (1997-2003), la « Cricca » d'Umberto Pagnini (1998-2002), le quintet de Gueorgui Kornazov (1998-2005), le quintet de Frédéric Favarel (1999-2003), Claude Nougaro (tournée « Embarquement Immédiat » 2000-2001), le « Paris-Jazz Big-Band » de Pierre Bertrand et Nicolas Folmer (2000-2012), le « New Quartet » de Didier Lockwood (2002-2007), le septet de Christian Escoudé (2003-2006), le quintet de Christophe Wallemme (2003-2007), le tentet d’Hervé Sellin (2005-2009), le « Blauklang Project » de Vince Mendoza (2008), le « New Large Ensemble de Carine Bonnefoy (2009-2013), le « All the Way » quartet de Frédéric Monino (2011-2013)…
En 2004, la sortie du disque « Soul Role » fait renaître ses aptitudes de leader.
Après avoir formé un quartet avec Frédéric Favarel (gt), Marc Buronfosse (cb) et Antoine Banville (bt), un autre projet sous son nom voit le jour à travers la sortie de l'album « Intra-Muros » en 2006.
En 2008, suite à une résidence à l’Opéra de Lyon, il met sur pied une toute nouvelle idée ; le quartet initial de Stéphane dialogue avec un Brass Band de sept cuivres, tous solistes d’exceptions. Les arrangements et orchestrations montés pour l’occasion ont été enregistrés en studio en juin 2008. Ces sessions font l’objet d’un album « Windmills Chronicles », sortie en octobre 2009.
Cette même année, l’Académie du Jazz lui décerne le prestigieux prix « Django Reinhart » du meilleur musicien français de l’année, ainsi que le prix du meilleur disque français de l’année pour « Windmills Chronicles ».
