Kleinman formed Bazooka Joe, a rock band, with John Ellis and friends from Orange Hill Grammar School, Burnt Oak, London.
[2] Bazooka Joe had a varied changing line up of musicians, notably Adam Ant and Arabella Weir, Mark Tanner (Sculptor), Chris Duffy (photographer).
Prior to Bond films, Kleinman directed music videos for musicians such as Madonna, Fleetwood Mac, Paula Abdul, Simple Minds, Wang Chung, Adam Ant and many others.
Kleinman has directed many television commercials for companies ranging from Smirnoff's Sea and Guinness' noitulovE, to pieces for Levi's, Johnnie Walker, Durex and Audi.
[3] Kleinman's appointment as title designer for the James Bond films placed greater emphasis on the use of modern technologies (such as computer-generated images) into the creation of the series' title sequences, as well as an arguably greater emphasis on the integration of elements of each film's respective plots within the musical sequences.