 He played with other prominent jazz musicians, in particular Dizzy Gillespie and Randy Weston, in addition to his solo work as bandleader.Payne received his first saxophone at the age of 13, asking his father for one after hearing "Honeysuckle Rose" performed by Count Basie with Lester Young soloing.Payne took lessons from a local alto sax player, Pete Brown.