Shortly after graduating, she formed Third Wind with Paula Kimper, another Eastman alumna. She also joined the ensemble Anomy, playing trumpet, synthesizer, and spoken word. In 1985, she joined an all-female brass section The You Threes, and began playing with the reggae band Steppin' Razor, with Jenny Hill and Nilda Richards. The You Threes became The Burning Brass when they toured globally with Burning Spear from 1986-1988. In 1991, she started her own group, Fearless Dreamer. She also played with Natalie Merchant at the 1998 Lilith Fair.
Fleming is a current member of blues/folk/world fusion/jazz group Hazmat Modine, playing trumpet on their second studio album, Cicada. She also plays with Metropolitan Klezmer and their all-female side project, Isle of Klezbos. With Metropolitan Klezmer, she also plays a shofar made from a kudu horn. Since 2006, she has played with the Black Rock Coalition orchestra. She also played trumpet in the second incarnation of Isis, an all-female horn band first founded in 1972.