Born in Wellington, Texas, Payne was raised in California and first played trumpet before switching to double bass in high school. His first major gigs occurred in the mid-1950s; he worked in the second half of the decade with Georgie Auld, Ornette Coleman, Maynard Ferguson, Calvin Jackson, Joe Maini, and Art Pepper. In 1958 he relocated to New York City, where he played with Tony Bennett, Chris Connor, and Mundell Lowe, then joined Herbie Mann and Astrud Gilberto for international tours. He also worked with Stan Getz around this time. He led his own ensemble with a rotating cast of sidemen, including Mike Abene, Joe Beck, and Gene Bertoncini.

Payne began playing bass guitar in 1964, and worked in popular and rock idioms as well as in jazz as a session musician for New York studio recordings. He played on releases by Loudon Wainwright III, Judy Collins, Roy Buchanan, Leonard Cohen (New Skin for the Old Ceremony, 1974), Janis Ian, Luiz Henrique, Harry Chapin, and Melanie Safka. His later jazz associations included Bobby Hackett, Jackie Cain, and Roy Kral.

With Melanie

• Gather Me (Buddah, 1971)
• Stoneground Words (Neighborhood, 1972)
• Madrugada (Neighborhood, 1974)

With Richie Havens

• Something Else Again (Verve, 1968)

With Janis Ian

• Stars (Columbia Records, 1974)
• Aftertones (Columbia Records, 1975)

With Loudon Wainwright III

• Album III (Columbia Records, 1972)

With Leonard Cohen

• New Skin for the Old Ceremony (Columbia Records, 1974)

With Judy Collins

• True Stories and Other Dreams (Elektra Records, 1973)

• "Don Payne". The New Grove Dictionary of Jazz. 2nd edition, ed. Barry Kernfeld.