He graduated from Berklee College of Music in 1994, and throughout the 1990s held a residency at Smalls, a jazz club in New York City. Known for his highly original harmonic and stylistic concepts, Klein has garnered much respect from the jazz community. He spent most of the 2000s in Argentina and Spain, though he still occasionally plays in the United States. He was commissioned by the MIT Wind Ensemble to write his first work for wind ensemble, Solar Return Suite, which was premiered on May 12, 2006. Klein has made several appearances with his band, Los Guachos, at the Village Vanguard since 2007.