Cecil McKenzie Payne was born December 14, 1922, in Brooklyn, New York, and grew up in Bedford-Stuyvesant, where he attended Boys High School. His father played tenor saxophone and kept records in the house; hearing Count Basie's band with Lester Young soloing on "Honeysuckle Rose" convinced the thirteen-year-old Payne to ask for a horn of his own. What he got was an alto, and he studied it with the Brooklyn alto saxophonist Pete Brown. Payne was drafted during World War II and spent his service years playing clarinet in Army bands, receiving his discharge in 1946. He liked to tell interviewers that his parents had pushed him toward dentistry, an idea he dismissed on the grounds that nobody would open their mouth for a Dr. Payne.

Payne's professional recording career began in 1946 with a Savoy session for trombonist J.J. Johnson, cut on alto. He switched to baritone that same year, and through trumpeter Roy Eldridge he was introduced to Dizzy Gillespie, joining Gillespie's postwar big band and staying with it until 1949. That put him at the center of bebop's most ambitious large-ensemble project, alongside bandmates including Ray Brown, John Lewis, and, briefly, Miles Davis. Payne played baritone on the December 22, 1947, RCA Victor date that produced "Cubana Be / Cubana Bop," the two-part George Russell arrangement built around the Cuban percussionist Chano Pozo, and on the band's February 1948 Paris concerts issued as Pleyel 48. He was also on "Ow!" and "Stay On It." Very few baritone players of the period could execute bebop's tempos and intervals at all, and Payne was among the first who could.

After leaving Gillespie he led two 1949 singles for Decca, "Block Buster Boogie" backed with "Angel Child" and "Hippy Dippy" backed with "No Chops," using a band that included pianist Duke Jordan and trumpeter Kenny Dorham. The next decade was spent largely as a freelance sideman: work with Tadd Dameron, a stint with Coleman Hawkins, and two years in Illinois Jacquet's band from 1952 to 1954. From the mid-1950s he became the baritone of choice for pianist Randy Weston, recording With These Hands..., Jazz a la Bohemia, and The Modern Art of Jazz in 1956 and touring Sweden with him. He also turned up on Gigi Gryce's October 22, 1955, orchestra session for Signal, released as Nica's Tempo, in a band with Oscar Pettiford, Art Blakey, and Horace Silver. Signal gave Payne his own leader dates in 1957: the quintet LP Cecil Payne, with Kenny Dorham, Duke Jordan, Tommy Potter, and Art Taylor, reissued by Savoy as Patterns of Jazz, and the co-billed A Night at the Five Spot with Phil Woods.

On April 20, 1957, Payne went into Rudy Van Gelder's Hackensack studio for a Prestige date co-led with fellow baritone saxophonist Pepper Adams, backed by Mal Waldron, Doug Watkins, and Art Taylor, with a young John Coltrane on tenor. Prestige first issued it in 1958 as one half of the 16 2/3 rpm sampler Baritones and French Horns, then, once Coltrane became a star, repackaged the same six titles in November 1963 under his name as Dakar, the title the music still carries. Payne recorded two albums for the Charlie Parker Records label in the early 1960s: Performing Charlie Parker Music (1961), with Clark Terry, Duke Jordan, and Ron Carter, and The Connection (1962), cut at RCA Victor Studios over three days that March. The title came from Jack Gelber's off-Broadway play, in which Payne appeared onstage as one of the musicians in the cast. He was also on Randy Weston's large-scale 1960 Roulette suite Uhuru Afrika, and through the 1950s he helped run his father's Brooklyn real estate business between engagements.

The 1960s and early 1970s took Payne through a run of demanding big-band chairs: Machito's Afro-Cubans from 1963 to 1966, a 1964 European tour with Lionel Hampton, roughly two years with Woody Herman from 1967, then three years with the Count Basie Orchestra beginning in 1969, and the New York Jazz Repertory Orchestra in 1974. His own recording resumed alongside it. A November 5, 1966, quartet set at Club 43 in Manchester, England, surfaced on the British Spotlite label as Brookfield Andante. Zodiac (The Music of Cecil Payne), an all-original program with Kenny Dorham, Wynton Kelly, Wilbur Ware, and Albert Heath, appeared on the musician-owned Strata-East label in 1973, dedicated to the memory of Kelly and Dorham, both of whom had recently passed away. Two Muse albums followed: Brooklyn Brothers, co-led with Duke Jordan in 1973, and Bird Gets the Worm in 1976, both with Al Foster on drums.

Through the 1980s Payne put most of his energy into Dameronia, the repertory band drummer Philly Joe Jones and trumpeter Don Sickler founded in 1981 to play Tadd Dameron's book, with Larry Ridley on bass; Payne stayed with the group after Jones's death in 1985 and recorded three albums with it. Glaucoma then cost him most of his sight, and he withdrew from performing for roughly six years. His return produced the best-documented stretch of his leader career: four albums for Chicago's Delmark label between 1993 and 2000, Cerupa, Scotch and Milk, Payne's Window, and Chic Boom: Live at the Jazz Showcase, all built around a younger front line of Eric Alexander, Harold Mabern, and Joe Farnsworth. He worked regularly at the Upper West Side club Smoke and at the Jazz Foundation of America's "Great Night in Harlem" benefits, and kept playing free concerts at New Jersey nursing homes. Cecil Payne passed away on November 27, 2007, in Stratford, New Jersey, of prostate cancer, at 84.

Payne's model was Lester Young, audible in the way he phrased long, unhurried melodic lines instead of hammering the baritone's low register, and he came to the horn by way of the alto, which left him with an agility most baritone players of the 1940s did not have. Where Harry Carney had made the instrument an orchestral foundation and Gerry Mulligan would soon make it a cool-toned melodic voice, Payne was the player who proved the baritone could handle Charlie Parker's vocabulary at Parker's tempos, and he built whole albums on that premise, including 1961's Performing Charlie Parker Music and 1976's Bird Gets the Worm. He was a working composer as well, with "Bosco," "Cerupa," "Chic Boom," "Brookfield Andante," "Bolambo," and "Cit Sac" all in circulation as published lead sheets, and he doubled on flute from the early 1970s onward. Critics have consistently framed him as underrecognized: he led only a handful of dates before his sixties and never kept a working band of his own for long, and reviewers treated the late Delmark records as belated proof of what he had been doing since 1946. AllMusic's Michael G. Nastos gave 1995's Cerupa four and a half stars and called it perhaps his best documented work.