Early in his career, Klein played with Nat Gonella in the late 1940s. He then played with Bill Le Sage and Kenny Baker before going on tour with Stan Kenton in 1956. Klein also worked with Stan Tracey for several years in the 1950s and 1960s. He also recorded with Tubby Hayes, Sammy Davis, Jr., Victor Feldman, Dudley Moore, and Champion Jack Dupree.
In the 1960s and 1970s Klein began doing work as a studio musician for English pop and rock bands. Klein played on The White Album, on the songs "Honey Pie" (clarinet) and "Savoy Truffle" (saxophone). He is also one of the four saxophonists (along with Ronnie Scott) who play on "Lady Madonna". Other credits include playing on records by Caravan.