His professional career began in New Orleans at 16, with his recording debut occurring in 1930. He worked in Ben Pollack's orchestra and then with Bob Crosby. He stayed with Crosby until the band broke up in 1942. He had his own band for a brief time after that before being drafted. However, he was discharged from the military early because of illness and settled in Los Angeles. After that he worked with Pete Fountain, appeared in most of Crosby's reunions, and did club work. Eddie also played with trumpeter Al Hirt.
He won numerous Playboy and Esquire Jazz polls, and during his many years on the west coast with, and following, his tenure with the Bob Crosby orchestra was considered one of the finest tenor men in the country. Miller finished a long and distinguished career playing several years with Pete Fountain, living in New Orleans. During that time, he was featured at several Regional Jazz festivals.