Beneke was born in Fort Worth, Texas. He started playing saxophone when he was nine, going from soprano to alto to tenor saxophones and staying with the latter. His first professional work was with bandleader Ben Young in 1935, but it was when he joined the Glenn Miller Orchestra three years later that his career hit its stride. Beneke said: "It seems that Gene Krupa had left the Goodman band and was forming his own first band. He was flying all over the country looking for new talent and he stopped at our ballroom one night listen to the Ben Young band. [...] Gene wound up taking two or three of our boys with him back to New York. wanted to take [Beneke but his sax section was already filled." Krupa knew that Glenn Miller was forming a band and recommended Beneke to Miller.