Estudià piano amb la seva mare. El 1924 anà a Nova York i conegué els millors pianistes de l’època, especialment James P. Johnson i Fats Waller. Aquest últim li donà classes informals i l’introduí en la tècnica de l’orgue. Mentrestant, treballà a cabarets de Harlem com a pianista i director musical de cantants de blues i d’espectacles de dansa i teatre. El 1927, durant una de les gires d’aquestes formacions, l’orquestra es dissolgué a Kansas City; Basie romangué en aquesta ciutat i, poc després, entrà als Blue Devils de Walter Page. Dos anys més tard s’integrà a la Bennie Moten’s Kansas City Orchestra, en la qual treballà fins el 1935, any en què, després de la mort sobtada del líder, l’orquestra es dissolgué. Basie formà, llavors, una orquestra nova amb antics companys i altres músics, que de seguida obtingué gran popularitat i, ja sota el nom de Count Basie Orchestra, se situà entre les millors formacions i les més innovadores de l’anomenada època swing (1935-45). Dificultats financeres l’obligaren a dissoldre-la el 1950, però Basie continuà treballant amb un grup més petit (de sis a nou músics). El 1952 l’orquestra es reorganitzà, i inicià una llarga sèrie de gires i gravacions que acabaren convertint-la en una institució i un model de la música de jazz.
L’estil de l’orquestra de Count Basie provenia de la tradició de les orquestres de jazz de Kansas City. S’organitzava al voltant de la secció rítmica, cosa que constituí per ella mateixa la primera innovació que l’orquestra aportà. El bateria Jo Jones, el contrabaix Walter Page, el guitarrista Freddie Green i el mateix Basie al piano aconseguiren crear més swing i alhora alleugeriren el timbre general. Foren, també, innovadors els arranjaments basats en riffs simples, directes i flexibles. Alguns eren recordats de memòria; d’altres, els escrivien membres de l’orquestra o arranjadors externs molt diversos.
L’eminència de Basie com a líder ha tendit a eclipsar la seva importància com a pianista. El seu estil era una simplificació del stride piano, amb frases curtes que evitaven l’ornamentació