En 2000-2002, Steve Lehman obtient une licence en composition, puis une maîtrise à l’université Wesleyan, où il étudie avec Anthony Braxton, Jay Hoggard et Alvin Lucier. En parallèle, il suit les cours de Jackie McLean à la Hartt School of Music. En 2012, à l’Université Columbia, il obtient un doctorat avec distinction en composition musicale sous la direction de Tristan Murail, George Lewis, Fabien Lévy et Fred Lerdahl. L’obtention d’une bourse Fulbright lui permet de se rendre en France pendant l’année universitaire 2002-2003, où il entreprend des recherches sur la réception des compositeurs expérimentaux afro-américains officiant en France pendant les années 1970. Il est par ailleurs titulaire d’une bourse Guggenheim (2015) et du Doris Duke Artist Award (2014).

En tant que saxophoniste alto, Steve Lehman opère dans les domaines du jazz et des musiques d’avant-garde. Le spectre de ses influences musicales, très étendu, lui permet de créer des passerelles entre le jazz et le hip-hop, la néo soul, le rap sénégalais et la musique électronique la plus abstraite (il propose par exemple un réarrangement d’un titre du duo Autechre sur l’album « The People I Love »).
Ses travaux récents en musique électroacoustique se concentrent sur le développement de modèles d’improvisation pilotés par ordinateur, basés sur l’environnement de programmation Max/MSP.

Steve Lehman se produit dans le monde entier accompagné de ses propres ensembles, ainsi qu’avec ceux dirigés par Anthony Braxton, Vijay Iyer, Bennie Maupin, Jason Moran, Georgia-Anne Muldrow, George Lewis, Meshell Ndegeocello et HPrizm d’Antipop Consortium, entre autres.
Ses pièces pour grand orchestre et ensembles de chambre sont jouées par l’International Contemporary Ensemble (ICE), So Percussion, l’American Composers Orchestra, le JACK Quartet, le PRISM Saxophone Quartet et le Talea Ensemble.

Steve Lehman publie également des articles et donne des conférences sur un large éventail de sujets, notamment la pédagogie du jazz ou la cognition du rythme. Ses travaux actuels portent sur les histoires croisées de la composition spectrale et de l’improvisation jazz.

Lehman est également pédagogue. Il donne successivement des cours de premier cycle à l’université Wesleyan, au Conservatoire National Supérieur de Musique et de Danse de Paris, à la New School University et à l’Université Columbia. Il donne des conférences au Amherst College, à l’UC Berkeley, à la Berklee School of Music, au Banff Centre, à la Royal Academy of Music de Londres ainsi qu’à l’Ircam, où il est également chargé de recherche en 2011.

Il est actuellement professeur de musique au California Institute of the Arts et vit à Los Angeles.