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, but little commercial success. He spent most of the '00s 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 in the last two years.
As of 2008, he is a member of the jazz faculty at Musikene (Centro Superior de Música del País Vasco), the Higher School of Music of the Basque Country, in San Sebastián.