Fowlkes first came to prominence in the 1980s as a member of The Lounge Lizards, which was led by saxophonist John Lurie. In 1987, he and saxophonist Roy Nathanson, both members of the Lounge Lizards, founded The Jazz Passengers, an eclectic group dedicated to putting entertainment and humor back into jazz.
Fowlkes has also performed as a sideman on over 20 jazz and rock CDs. In addition to The Jazz Passengers and The Lounge Lizards, he has performed with bassist Charlie Haden's reunited Liberation Music Orchestra in 1996, and with the alumni Ellington Orchestra led by Louie Bellson. He has also performed or recorded with Bill Frisell's quartet, as well as with John Zorn, Marc Ribot, Henry Threadgill, Sheryl Crow, Andy Summers, Cibo Matto, Jeb Loy Nichols, and comedian Harry Shearer. He has also performed with the Kansas City All-Stars, appearing in Robert Altman's 1996 film Kansas City with this group.
With his six-piece band, Catfish Corner, Fowlkes released his first album as leader, entitled Reflect, in 1999.
Curtis recorded with the Charlie Hunter Quintet in 2003 on the album "Right Now Move".