Donald Matthew Redman was born in Piedmont, West Virginia on July 29, 1900. His father was a music teacher, and by age 12 he was proficient on wind instruments ranging from trumpet to oboe as well as piano. He studied at the Boston Conservatory, then joined Billy Page's Broadway Syncopaters in New York City.
In 1923 Don Redman joined the Fletcher Henderson orchestra, mostly playing clarinet and saxophones. He soon began assisting Henderson in writing arrangements, and Henderson and Redman did much to formulate the sound that was to become big band swing.
In 1927 Redman joined the Detroit, Michigan based band McKinney's Cotton Pickers, who he played with and arranged for through 1931. Redman then formed his own band, which got a residency at the famous Manhattan jazz club Connie's Inn. Redman's band got a recording contract with Brunswick Records and a series of radio broadcasts. Redman's band was even featured doing the soundtrack of a Betty Boop cartoon ("I Heard") featuring Redman compositions. On the side Redman also did arrangments for other band leaders and musicians, including Paul Whiteman, Isham Jones, and Bing Crosby.