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. He had already led several informal bands before King Fleming and His Swing Band first performed in September 1942. When he was drafted into the U.S. Army in July 1943, the band continued performing under the leadership of other bandmembers until too many of its members had been called up for it to be viable.
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. 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.
In 1950 he was a member of the Dallas Bartley Quartet, with Johnny Thompson (tenor sax) and Oliver Coleman (drums), and that summer he recorded as a session pianist for the vocal group, the Dozier Boys, at their recording session for Chess Records. Later that year he joined Oliver Coleman's Palmaires; the other members were Nelson Berry (tenor saxophone) and Sylvester Hickman (bass).
In 1954 he finally recorded under his own name, on the Blue Lake label, with John Neely (tenor saxophone); Russell Williams (bass); Aubrie Jones (drums); Lorez Alexandria (vocals) and in 1955 for the Chess label. The Chess brothers invited him back the following year, again with vocalist Lorez Alexandria, to record "Stompin' at the Savoy". In 1957, his group backed Lorez Alexandria on her first two albums for the King label, and collaborated with Muhal Richard Abrams, who wrote arrangements for a King Fleming-led big band.
Between 1960 and 1965, he recorded three piano trio albums for Argo and Cadet Records, which were Phil and Leonard Chess's jazz labels. He also appeared on two singles released locally by singer George Green.
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.
- 1961: Misty Night - King Fleming Trio
- 1962: Stand By
- 1965: Weary Traveler
- 1996: King! The King Fleming Songbook
- 2000: The King and I