Sonny Payne's father was Wild Bill Davis's drummer Chris Columbus. After early study with Vic Berton, in 1944 Payne started playing professionally around New York with the Dud and Paul Bascomb band, Hot Lips Page, Earl Bostic (1945–1947), Tiny Grimes (between 1947 and 1950), and Lucille Dixon (1948).
From 1950 to 1953, Payne played with Erskine Hawkins' big band, and led his own band for two years, but in late December, 1954, he made his most significant move, joining Basie's band for more than ten years of constant touring and recording. He was originally asked only to temporarily fill in for Basie's ailing regular drummer, but Payne's flashy style was such a hit that he was immediately hired to be Basie's permanent drummer.
He left Basie in 1965, leading his own trio and touring with Illinois Jacquet in 1976. He was Frank Sinatra's personal drummer for all of the singer's appearances with the Count Basie Orchestra in 1965 and 1966; in fact, whenever Sinatra sang with Basie in the 1960s, Payne was the drummer. He later rejoined Basie at his wife's urging as the regular drummer (1972–1974).
Most of the rest of his career, however, was spent in the Harry James band, which he joined in 1966, and with which he was working when he died of pneumonia at the age of 52. When he was dying in the hospital, Harry James paid all of his medical bills and subsequent funeral costs.