The Count Basie Orchestra grew directly out of the Kansas City territory-band scene of the early 1930s. Pianist William James Basie — born August 21, 1904, in Red Bank, New Jersey — joined bandleader Bennie Moten's Kansas City Orchestra in 1929, and stayed until Moten's sudden death in April 1935 following a botched tonsillectomy. Rather than fold into another leader's band, Basie assembled his own nine-piece group, initially billed as the Barons of Rhythm, built largely from Moten alumni: bassist Walter Page, drummer Jo Jones, alto saxophonist Buster Smith, tenor saxophonist Lester Young, trumpeters Oran "Hot Lips" Page and Joe Keyes, and blues shouter Jimmy Rushing. The band became the house group at Kansas City's Reno Club, broadcasting late-night sets over the radio — broadcasts during which, according to the band's own oft-repeated history, an announcer decided "Bill Basie" needed more stature next to bandleading peers like Duke Ellington and Earl Hines, and began introducing him on air as "Count" Basie. In 1936, producer and critic John Hammond heard one of those broadcasts by chance while scanning the radio dial and traveled to Kansas City to hear the band in person, becoming the connection that moved Basie's group out of the territory-band circuit entirely.

Hammond's advocacy brought the band to New York in 1936-37 and expanded it to a standard 13-piece lineup. Its first recordings for Decca were cut beginning in January 1937, and in March 1937 guitarist Freddie Green joined — the final piece of what would become, alongside Page and Jones, the "All-American Rhythm Section": a rhythm section built on Green's understated four-to-the-bar chordal comping, Page's smooth walking bass, and Jones's innovation of keeping time on the hi-hat and ride cymbal rather than the bass drum, producing a lighter, more forward-driving pulse than most big bands of the era. On top of that foundation, the Basie band built its identity on riff-based "head arrangements" — tunes worked out collectively in rehearsal and memorized rather than formally notated — a working method carried over directly from the Kansas City jam-session tradition. That approach produced the band's breakout hits: "One O'Clock Jump," recorded for Decca on July 7, 1937 and named for the hour it was typically played during the Reno Club's late-night broadcasts, and "Jumpin' at the Woodside" (1938). Jimmy Rushing was the band's featured blues vocalist through this period; Billie Holiday sang with the band briefly in 1937 but, tied to a rival label's contract, never recorded with it, and Helen Humes took over as featured vocalist in 1938.

The 1940s brought both wider ambition and real disruption. The band increasingly relied on outside arrangers — Andy Gibson, Buster Harding, Jimmy Mundy — moving its sound somewhat away from pure Kansas City riffing toward more polished ensemble writing. A recording ban from 1942 to 1944 hurt the band financially, and the wartime draft took two key members, drummer Jo Jones and tenor saxophonist Lester Young, in 1944; younger players including Buddy Rich, Illinois Jacquet, and Paul Gonsalves filled in. Economic pressure on big bands generally forced Basie to break up the full orchestra for stretches in 1948 and again from 1950 to 1952, leading a much smaller combo — at various points featuring Buddy Rich, Serge Chaloff, and Buddy DeFranco — before reassembling the full big band in 1952. That reconstituted group became known, informally, as the "New Testament" band, distinguishing it from the "Old Testament" swing-era orchestra of the 1930s-40s.

The New Testament band, powered by arrangers Neal Hefti, Ernie Wilkins, Frank Foster, and later Sammy Nestico, produced the records now most closely associated with the "Basie sound": Count Basie Swings, Joe Williams Sings (1955), which introduced vocalist Joe Williams and the hit "Every Day I Have the Blues" (later inducted into the Grammy Hall of Fame); April in Paris (recorded 1955-56, released 1957 on Verve); and Basie, recorded in October 1957 for Roulette and released in January 1958 — an album so identified with its mushroom-cloud cover art and "E=MC²" motif that it became universally known as The Atomic Mr. Basie, and which introduced the standard "Li'l Darlin'." The band toured internationally through this period, including Europe in 1954 and Japan in 1963, and recorded two studio collaborations with Frank Sinatra — Sinatra-Basie: An Historic Musical First (1962, arranged by Neal Hefti) and It Might As Well Be Swing (1964, arranged by Quincy Jones) — along with dates backing Ella Fitzgerald and Sarah Vaughan. Basie died April 26, 1984, in Hollywood, Florida, a few months after the release of his final studio album, 88 Basie Street (Pablo, 1984, arranged by Sammy Nestico), which won the Grammy for Best Jazz Instrumental Performance, Big Band that year.

The orchestra did not disband with its founder. Trumpeter and arranger Thad Jones led the band from 1985 to 1986, followed by saxophonist Frank Foster (1986-1995), Grover Mitchell (1995-2003), trombonist Bill Hughes (2003-2010), drummer Dennis Mackrel (2010-2013), and trumpeter Scotty Barnhart, who has directed the band since 2013. Under Barnhart the orchestra remains an active touring and recording unit; its 2023 album Basie Swings the Blues (Candid Records), pairing the orchestra with blues artists including Buddy Guy, Keb' Mo', and Shemekia Copeland, won the 2024 Grammy for Best Large Jazz Ensemble Album — extending a recording history, under one name, that by then spanned close to nine decades.

The Basie band's most durable contribution to jazz is really a rhythmic idea: the All-American Rhythm Section's shift toward a lighter, more forward-moving 4/4 pulse — Walter Page's steady walking bass, Freddie Green's spare, largely unamplified chordal guitar comping (famously not soloing, just keeping time), and Jo Jones's move of timekeeping onto the cymbals rather than the bass drum — became the template against which essentially every subsequent big-band and small-group rhythm section was measured. Basie's own piano style reinforced the same instinct toward economy: sparse, perfectly placed single notes and short phrases rather than dense chording, a "less is more" approach that let the band's riffs and soloists carry the weight. That combination of a supple, driving rhythm section under simple, punchy, often collectively-composed riffs — the "head arrangement" tradition inherited from Kansas City's competitive jam-session culture — defined the band's 1930s-40s sound and gave swing-era dancers and listeners alike an instantly identifiable groove. The 1950s-60s "New Testament" band, arranged by figures like Neal Hefti, Frank Foster, and later Sammy Nestico, translated that same riff-based sensibility into more fully notated, precision-drilled ensemble writing without losing its blues-rooted, riff-driven core — a sound so influential that "swinging" itself became loosely synonymous with the Basie band's particular brand of relaxed, hard-driving power, and one that shaped everything from Frank Sinatra's big-band vocal recordings to the working vocabulary of virtually every jazz big band that followed it.