In 1992 Leonhart was honored with the first Grammy Award for outstanding high school musician in the US (he attended Fiorello H. LaGuardia High School). At the time, he was the youngest Grammy recipient to date. He was 17 years old. In February of that same year ABC World News named him "Person of the Week."
Leonhart has performed with Steely Dan since 1996, recording two albums with them, including 2000's Grammy winning Album of the Year Two Against Nature on which he was a featured soloist, arranger and conductor. He is also co-producer of Donald Fagen's fourth solo album Sunken Condos released in 2012.
Over his career he has performed and/or recorded with such diverse artists as A Tribe Called Quest, Arif Mardin, Arto Linsday, Bill Frisell, Bill Withers, Bobby McFerrin, Bonnie Raitt, Brian Eno, Busta Rhymes, Caetano Veloso, D.J. Spooky, David Byrne, Henry Mancini, James Brown, John Barry, Joshua Redman, Lenny Kravitz, Levon Helm, Mark Ronson, Michael McDonald, Mos Def, Natalie Merchant, Q-Tip, Raekwon (Wutang Clan), Slash (Guns and Roses/ Velvet Revolver), Steven Tyler (Aerosmith), Todd Rundgren, and Wynton Marsalis.
Leonhart recorded with Yoko Ono as a featured member of The Plastic Ono Band in 2009 for her album, Between My Head and the Sky., and again in 2013 on her album Take Me to the Land of Hell. Leonhart has appeared on two albums by the group Monkey House, in 2012 on Headquarters, and in 2016 on Left.
In 2015, Leonhart collaborated with the Antibalas and The Dap-Kings horn sections, Mark Ronson, and Bruno Mars to record "Uptown Funk" and other tracks off of Mark Ronson's 2015 album Uptown Special.
After 40 plus recordings as the house trumpet player for Truth and Soul Records, the Brooklyn-based funk and soul label released Leonhart's heavy-funk concept album Seahorse and the Storyteller in 2009.
Michael Leonhart is the son of Jay Leonhart, noted jazz bassist, and the brother of Carolyn Leonhart, vocalist.Aardvark Poses (Sunnyside, 1995)
Glub Glub vol. 11 (Sunnyside, 1997)
Slow (Sunnyside, 2002)
The Suzy Lattimore EP (self-released, 2005)
The Ballad of Minton Quigley (self-released, 2006)
Hotel Music (St. Ives, 2008)
Seahorse & the Storyteller (Truth and Soul 2010)
With Nels ClineLovers (Blue Note, 2016)