E. framträdde först som vokalist och trumpetare i Earl Hines’ orkester. År 1944 bildade han egen orkester, jazzhistoriskt betydelsefull eftersom ett flertal av den unga bebop-generationens yppersta solister kom att ingå. Från slutet av 1940-talet framträdde E. huvudsakligen som populärsångare, där hans kraftfulla baryton blev stilbildande i långsamma balladtolkningar.