Flemming was born Nicolaiih El-Michelle, and was of North African descent. Flemming studied music and played mellophone and euphonium at Dobbs Chauncey School in Dobbs Ferry, New York before switching to trombone. He was a member of James Reese Europe's 15th New York National Guard Band with Eugene Mikell, and then Europe's 369th U.S. Infantry Band in France in 1917. After the war, he also studied at the Frank Damrosch Conservatory in New York, playing cello there; later studied at the St. Cecilia Academy in Florence and the University of Rome. He played with Fred Tunstall in 1921 and recorded with Johnny Dunn before joining Sam Wooding and Bobby Lee's band in Philadelphia. Wooding left the U.S. to tour Europe in the mid-1920s, and Flemming continued to play with him Stateside when they returned in 1927. Late in the 1920s he joined Lew Leslie's Blackbirds show, which toured London and Paris toward the end of the decade.
Around 1930 he formed his own band in Europe, the International Rhythm Aces, in addition to doing continued work with Wooding. They collaborated in Berlin, then Flemming found work accompanying Josephine Baker. He appeared in Buenos Aires with his ensemble early in the decade. In 1933 he played in Paris, and then made tour appearances in Calcutta, Shanghai, and Ceylon. In the mid-1930s he also worked as a vocalist in Berlin (1935–37), and played with Sestto Carlin's Society Orchestra in Italy. In 1936 he interpreted for the U.S. at the Olympic Games.
Flemming returned to the United States at the end of the 1930s to play with Earl Hines, but was prevented from joining the band due to problems with the city musicians' union. He played with Fats Waller in Cicero, Illinois from 1940 to 1942, singing and playing trombone. After time playing with Noble Sissle, he moved to California and worked for the Internal Revenue Service from 1943 to 1949. He occasionally appeared in films at this time, including Pillow to Post and No Time for Romance.
In 1949, he took a vacation to New York City and elected to move there. He played freelance for a time, then under Red Allen from 1953 to 1958. He moved to Spain in 1964 and held residencies in Madrid, Torremolinos, and Malaga; near the end of his life he recorded with Albert Nicholas and Walter Bishop, Sr.. After more time in Italy and Germany, he returned to the U.S. in 1976 and died shortly thereafter.
- Herb Fleming at Allmusic
- Leonard Feather and Ira Gitler, The Biographical Encyclopedia of Jazz. Oxford, 1999, pp. 227–228.