A classmate of Sonny Cohn, after playing trombone in the McKinley High School band, Fleming went on to study at the Midwest College of Music.
[1] Discharged in 1945, Fleming started doing session work in Los Angeles and joined Johnnie Alston & His All Stars for recording dates backing Wynonie "Blues" Harris on Apollo.
[1] Johnny Alston and His Orchestra later signed for the Bihari Brothers' Modern label, and Fleming and Al "Cake" Wichard were joined by Addison Farmer.
By mid-1946, Fleming had joined the Swing combo Oliver "King" Perry's Pied Pipers with Norman Bowden (trumpet); George "Happy" Johnson (trombone); Wesley Prince (bass) and Joe Harris (drums) before returning to Chicago to lead his own King Fleming's Four with Jay Peters (tenor sax), "Hog" Mason (bass), and Tommy Hill (drums) and getting a write-up in Down Beat for June 18, 1947.
After many years during which his trio worked steadily in the Chicago area without drawing interest from the recording industry, King Fleming resurfaced on the Southport label in 1996.