Il pianista William Allen "Count" Basie (1904), di Kansas City, formò il gruppo Barons of Rhythm nel 1936, che presto assunse i sassofonisti tenore Lester Young e Herschel Evans, i trombonisti Dicky Wells e Benny Morton, il cantante Jimmy Rushing e (in sostituzione di Oran "Hot Lips" " Page) il trombettista Wilbur "Buck Clayton" Dorsey, spingendoli con la formidabile sezione ritmica di Basie al piano, Freddie Green alla chitarra, Walter Page al basso e Jo Jones alla batteria.
I pilastri di quella formazione furono messi alla prova in Lady Be Good (ottobre 1936) di George Gershwin e Shoe Shine Boy (novembre 1936) di Saul Chaplin, accreditati alla Jones-Smith Incorporated, un quintetto con Basie, Page, Jones, Young e un trombettista che presentava i primi (rivoluzionari) assoli di Young.
La big band di Basie indulgeva in uno stile più blues basato sul riff (spesso suonato all'unisono) e su un contrappunto "chiamata e risposta" tra le sezioni degli ottoni e delle ance, enfatizzando al contempo l'improvvisazione estesa: One O'clock Jump (luglio 1937), un 12-bar blues che divenne la loro prima hit, Topsy (agosto 1937), composto dal chitarrista e trombonista di Moten, Eddie Durham, Jumpin' at the Woodside (agosto 1938), Stop Beatin' Round the Mulberry Bush (agosto 1938), Sent for You Yesterday (febbraio 1938), Goin' to Chicago Blues (febbraio 1939), Blue And Sentimental (giugno 1938), con l'assolo più famoso di Evans.
Molti di questi pezzi erano show personali di Rushing. Young contribuì a Taxi War Dance (marzo 1939), Lester Leaps In (settembre 1939), che ricorda I Got Rhythm di George Gershwin, e Tickle Toe (marzo 1940).
Evans morì di cardiopatia nel 1939, a soli 29 anni, e Young lasciò l'orchestra l'anno successivo, ma l'orchestra continuò a trovare nuovi talenti e realizzare nuove hit, come Open the Door Richard (gennaio 1947) e Every Day I Have the Blues (maggio 1955), con il nuovo cantante Joe Williams.

Basie è morto di cancro nel 1984, all'età di 79 anni.