Le 21 août 1904 à Red Bank (New Jersey, Etats-Unis), la famille Basie accueille son dernier-né, William James. Elevé par un père employé de maison et une mère lavandière, le jeune garçon prend tôt des leçons de piano, mais ne brille guère pour ce qui est du reste de sa scolarité, et quitte tôt l’école. Encore adolescent, il est engagé un peu par hasard pour accompagner un spectacle au piano et apprend vite à improviser des airs. Attiré par la batterie, il décide finalement, à l’âge de quinze ans, de se consacrer exclusivement au piano.
Une rencontre avec Sonny Greer, le batteur de Duke Ellington, lui permet de décrocher ses premiers engagements auprès d’orchestres de jazz. Il réalise plusieurs tournées au milieu des années 1920, rencontrant à Kansas City et surtout à Chicago la crème des jazzmen de l’époque. En 1925, il est engagé au club Leroy’s et y rencontre Fats Waller, qui lui apprend à maîtriser l’orgue. Améliorant sa maîtrise technique au fil des rencontres et des engagements, William Basie rejoint l’orchestre Walter Page and His Famous Blue Devils et réalise plusieurs tournées avec la troupe, gagnant au passage son sobriquet de « Count » Basie, selon la tradition du milieu du jazz d’affubler ses musiciens vedettes de titres royaux (« King », « Queen ») ou, plus modestement, aristocratiques (« Earl », « Baron », « Duke »).
Il rejoint en 1929 l’orchestre de Bennie Moten, cumulant des fonctions de pianiste et d’arrangeur. Count Basie s’établit à Kansas City pour collaborer avec Moten, mais l’orchestre est vite plongé dans la tourmente : fâché avec le reste de ses musiciens, Moten est exclu de sa propre troupe et Count Basie doit le remplacer, rebaptisant l’orchestre Count Basie and His Cherry Blossoms. L’expérience ne dure pas et il retourne bientôt travailler avec Moten, dans un nouvel orchestre. Leur collaboration s’achève finalement en 1935, quand Bennie Moten meurt des suites d’une opération chirurgicale. Count Basie fonde un nouvel orchestre, qui prend en 1936 le nom de Count Basie and his Baron of Rhythm : la troupe multiplie les engagements dans les clubs et commence à passer à la radio. D’une session plus ou moins improvisée par la troupe, Count Basie tire la chanson « One O'Clock Jump », qui devient l’un de ses airs les plus connus.
L’orchestre de Count Basie se distingue par un son à la fois dynamique et maîtrisé, garanti par un ensemble de collaborateurs hors pair, parmi lesquels on peut compter Lester Young (saxophone), Harry Edison (trompette) ou Freddie Green (guitare). La troupe multiplie également les collaborations avec des chanteurs de blues réputés, comme Joe Williams ou Jimmy Rushing. Chef d’orchestre autant que pianiste virtuose, Count Basie assure la cohérence de sa troupe en choisissant des collaborateurs – musiciens et arrangeurs – de tout premier plan, s’affirmant comme l’un des maîtres du style Jazz de Kansas City.
New York en feu
Dans la seconde moitié des années 1930, Count Basie et ses musiciens s’installent à New York et, après avoir quelque peu travaillé pour adapter leur style d’interprétation au public local, décrochent un contrat d’enregistrement chez Decca. Le producteur John Hammond assure à la troupe une recrue de poids en leur assurant la collaboration de Billie Holiday : lors d’une mémorable Battle of the Bands, compétition entre orchestres de jazz organisée au club Savoy, l’orchestre de Count Basie réussit à remporter la victoire face à celui de Chick Webb, qui comptait pourtant la collaboration d’Ella Fitzgerald en personne.
Grâce à ce spectaculaire succès, la troupe des gars de Kansas City s’impose définitivement auprès du public new-yorkais. Billie Holiday étant partie pour travailler avec l’orchestre d’Artie Shaw, Count Basie la remplace par Helen Humes. Grâce à ses chanteuses successives, et au soutien du réseau CBS, l’orchestre de Count Basie connaît un bond de notoriété et s’affirme comme l’un des piliers du jazz : on les voit participer à la comédie musicale Reveille with Beverly et à des galas de soutien aux troupes américaines durant la Seconde Guerre mondiale.