After enrolling at Howard University, Eckstine won first place in a talent contest in Washintgon, D.C., and decided to leave school to sing full time. Performing at first in Washington, Eckstine moved to Chicago in 1937. Hired by legendary pianist and bandleader Earl Hines, Eckstein continued to sing with the Hines band for four years, broadening his vocal talent and forging relationships with innovating jazz musicians. Eckstine and the Hines band produced several major jazz songs including the bluesy Jelly, Jelly (1940). In 1943, Eckstine started his own jazz orchestra, which is considered prolific. He assembled a constellation of jazz luminaries. Sarah Vaughan, Miles Davis, Charlie Parker, Dizzy Gillespie, Fats Navarro, Gene Ammons, Dexter Gordon, and Art Blakely were among those who passed through Eckstine's band.¹¹¹

Eckstine is credited with forming the first bebop big band, incorporating the major elements of bebop (the smoothness of swing, irregular rhythms, and harmonic experimentation) and adapting the sound to a big-band format. The big band bebop genre would take off under Gillespie, but offered little commercial success to Eckstine. Instead, he was celebrated as a sex symbol for his romantic ballads. His style was carefully crafted—narrow ties, relaxed jackets became Eckstine's signature style and set fashion trends. In 1944 Eckstine's band toured the South and several promoters dropped the segregation requirement, foreshadowing his immense success with both black and white audience. The tour grossed over $100,000 in ten weeks.

After World War II, Eckstine toured with the Count Basie Orchestra and was signed to a recording contract with MGM. His I Apologize, Fools Rush In and Everything I Have is Yours became huge hits, and by 1950 Eckstine was MGM's top-selling artist.¹¹²