Treballà en un espectacle itinerant abans d’unir-se als Blue Devils, de Walter Page (1927-29), i a la Bennie Moten’s Kansas City Orchestra (1929-35), dues de les formacions més importants en la creació de l’estil Kansas, de les quals sorgí l’orquestra de Count Basie. Durant aquests anys, Rushing creà, amb la seva càlida veu de tenor, un model d’interpretació vocal de blues, el blues shouter, que s’emmirallà amb la fluïdesa rítmica dels seus companys instrumentistes. El 1936 anà amb Basie a Nova York, on romangué fins el 1950, i fou una peça clau en l’èxit de la seva orquestra. Després treballà amb grup propi i com a solista, fent gires amb altres formacions, incloses les de Buck Clayton i Benny Goodman. En 1971-72 actuà amb Zoot Sims a Nova York. Els seus millors enregistraments de l’època clàssica, entre els quals cal incloure el seu èxit Sent For You Yestersday, són recollits en el CD Mr. Five by Five.