W różnym czasie występowali w niej bowiem tacy muzycy jak saksofoniści Ben Webster, Coleman Hawkins, Benny Carter i Frank Foster, trębacze Charles Freeman Lee i Cootie Williams, oraz bandlider Fletcher Henderson.
W 1941 otrzymał powołanie do wojska, ale wtedy po badaniach medycznych i ujawnieniu gruźlicy, na którą chorował od kilku lat, trafił do szpitala. Podczas półrocznej hospitalizacji jeden z pacjentów zapoznał go z podstawami teorii muzyki i rozbudził zainteresowanie tą dziedziną. Russell skomponował wtedy dla Benny’ego Cartera utwór New World.
Po wyjściu ze szpitala wyjechał do Chicago i został perkusistą w zespole Benny’ego Cartera. Kiedy jednak usłyszał grę Maksa Roacha, ustąpił mu miejsca w orkiestrze i podjął dwie decyzje: o zaprzestaniu gry na perkusji i poświęceniu się komponowaniu oraz teorii muzyki. Zainspirowany pianistyczną twórczością Theloniousa Monka, przeprowadził się do Nowego Jorku i dołączył do grupy młodych innowatorów jazzu skupionych wokół aranżera i kompozytora Gila Evansa. Regularnymi bywalcami mieszkania Evansa na Manhattanie byli: Miles Davis, Charlie Parker, Dizzy Gillespie, Gerry Mulligan i John Lewis. W latach 1945–1946 nawrót choroby spowodował jego ponowny pobyt w szpitalu, tym razem przez szesnaście miesięcy.