Frank Benjamin Foster III was born September 23, 1928, in Cincinnati, Ohio. He developed an ear for music by age five, listening to classical broadcasts and hearing opera with his mother at the Cincinnati Zoo pavilion. He began clarinet lessons at eleven and switched to saxophone at thirteen after a teacher pointed out that the horn had more work in dance bands. By his senior year of high school he was organizing and writing for his own 12-piece band with no formal training in arranging. He enrolled at Wilberforce University but left before graduating in 1949, when trumpeter Snooky Young invited him to Detroit for a seven-week engagement; the Detroit scene he found there, including Barry Harris and Kenny Burrell, convinced him to stay rather than finish his degree.

In Detroit, Foster worked the Blue Bird Inn alongside Wardell Gray and Milt Jackson, and crossed paths early with drummer Elvin Jones and with Thelonious Monk. The Army drafted him in 1951, and he served in Korea with the 7th Infantry Division, at one point going AWOL to San Francisco to sit in with Dexter Gordon. Discharged in 1953, he came across a Down Beat article on Count Basie's orchestra while still stationed overseas, and a chance meeting after his return home led directly to a chair in the band. He joined that July and stayed until 1964, a decade that made his reputation as both a tenor soloist and, increasingly, as one of the orchestra's key composer-arrangers.

Foster's writing shaped what became known as Basie's "New Testament" band. In 1955, at a rehearsal in Philadelphia's Pep's Bar, he introduced a chart that by his own account sounded at first "like a 43-car pile-up"; worked into shape, it became "Shiny Stockings," first recorded for Verve on January 4, 1956, and eventually one of the most widely played big-band charts in the jazz repertoire, later fitted with lyrics by Jon Hendricks. Alongside arrangers Neal Hefti and Ernie Wilkins, Foster helped build the book behind the Count Basie Orchestra's signature 1950s records, while his own bebop-inflected tenor, paired opposite the cooler-toned Frank Wess in the reed section, gave the band a running "Two Franks" contrast that became one of its signatures. He also led his own Basie-sideman dates on the side: Here Comes Frank Foster (1954, Blue Note), drawing on Basie personnel, and No 'Count (recorded March 1956, Savoy), a sextet session built around Frank Wess, trombonists Henry Coker and Benny Powell, Kenny Burrell, bassist Eddie Jones, and drummer Kenny Clarke.

After leaving Basie in 1964, Foster worked briefly with Woody Herman's band, freelanced widely, and moved increasingly into teaching, including a 1971 artist residency at the New England Conservatory, ongoing work as a music consultant in New York City's public schools from 1971 on, and a full-time assistant professorship in Black Studies at SUNY Buffalo from 1972 to 1976. He played with Illinois Jacquet and with Duke Pearson's big band in 1968, toured and recorded with the Thad Jones/Mel Lewis Orchestra in 1972 and 1975, and served two stints, 1970-1972, in Elvin Jones's working quartet and quintet. In this period he organized his own groups, most durably The Loud Minority, an 18-piece "concert jazz orchestra" that recorded its debut album for Mainstream in 1972 and toured Europe and Japan; he also led Living Color, the Non-Electric Company, and Swing Plus at various points, and recorded the Blue Note session Manhattan Fever (1968) and the Prestige albums Fearless Frank Foster (1965) and Soul Outing! (1966). His writing reached beyond his own bands, too: he orchestrated Dizzy Gillespie's "Con Alma" for the London Philharmonic Orchestra and composed the "Lake Placid Suite" for the 1980 Winter Olympics.

The 1980s brought a run of reunions and new leadership. Beginning in 1983 he re-teamed with Frank Wess in a co-led quintet, documented on Two for the Blues (recorded October 1983, released 1984, Pablo) and Frankly Speaking (recorded December 1984, released 1985, Concord Jazz). In January 1985 he and baritone saxophonist Pepper Adams co-led the Muse Records session Generations, a quintet date rounded out by pianist Noreen Grey, bassist Earl Sauls, and drummer Glenn Davis; that September, Foster was among the musicians, alongside Dizzy Gillespie, Kenny Burrell, and Tommy Flanagan, who turned out for a benefit concert for Adams as he underwent treatment for the lung cancer that killed him days later, on September 10, 1986. Weeks after that concert, Foster succeeded Thad Jones, who had led the post-Basie ghost band since 1985, as musical director of the Count Basie Orchestra, a post he held from 1986 to 1995. He balanced preserving Basie's book with adding his own new charts, winning Grammy Awards for his arrangements of "Deedles' Blues" (1987) and "Basie's Bag" (1988) along the way.

After stepping down from the Basie band in 1995, Foster returned full-time to his own groups and kept recording into the 2000s, including Leo Rising (1996, Arabesque), We Do It Diff'rent (2003, Mapleshade), and Endless Fingers (2005, Arabesque). He received an honorary doctorate from Central State University in 1987, the Benny Golson Jazz Master Award from Howard University in 1998, and the National Endowment for the Arts' NEA Jazz Masters Award in 2002. A stroke in 2001 left him unable to play saxophone, and he handed leadership of The Loud Minority to Cecil Bridgewater, but he kept composing and arranging at home using notation software with playback, work he said gave him the same creative satisfaction as performing because a score could be revised where a live solo could not. In 2010 and 2011, with help from a Rutgers School of Law legal team, he recovered full songwriting royalties on "Shiny Stockings" and his other Basie-era compositions, decades after signing away his publishing rights as a young sideman who, in his own telling, simply didn't know better. He had been married to his wife and longtime personal manager, Cecilia Foster, for nearly 45 years. Frank Foster died of kidney failure on July 26, 2011, in Chesapeake, Virginia, at age 82.

Foster came into the Basie band as a bebop-schooled tenor player in a swing institution, and the tension never entirely resolved. By his own account, Basie's musicians thought his early charts and solos sounded strange next to the older "Old Testament" book, but Basie encouraged the new sound anyway, and it became a defining color of the "New Testament" band. His tenor drew on the muscular, harmonically busy vocabulary of the boppers (Sonny Stitt above all) rather than the airier lyricism of Basie's earlier stars Lester Young and Herschel Evans, and his pairing with the cooler, Websterish Frank Wess, the "Two Franks," gave the Basie reed section a contrast audiences and critics came to recognize instantly. As a writer he was equally comfortable inside the compact, riff-driven Basie formula ("Shiny Stockings" remains one of the most-recorded big-band charts in the repertoire) and in more expansive, soul-jazz and modal settings on his own dates with The Loud Minority. His two Grammy-winning arrangements for the Basie ghost band in the late 1980s, along with a body of composition that ranged from Olympic ceremonial music to an orchestration of a Dizzy Gillespie standard for a symphony orchestra, reflected a writer as comfortable serving an institution's sound as expanding it.