Die Band entstand 1930 im New Yorker Stadtteil Harlem; ihr erster Bandleader war der Saxophonist Bingie Madison. Vorübergehend nannte sich die Formation „Coconut Grove Orchestra“ und änderte den Namen in Mills Blue Rhythm Band, als Irving Mills 1931 ihr Manager wurde. Sie galt als eine der bedeutendsten Swingbands der 1930er Jahre und firmierte auch unter den Bezeichnungen „Blue Rhythm Band“, „King Carter’s Royal Flush Orchestra“, „Blue Rhythm Boys“, „Mills Music Masters“, „Harlem Hot Shots“. Kurze Zeit fungierte sie auch als Begleitgruppe von Louis Armstrong.
Plattenaufnahmen entstanden erst am 4. Oktober 1934 für Columbia mit „Out Of Dream“ / „Let’s Have A Jubilee“, und bereits mit der am 5. Dezember 1934 unter Leitung von Lucky Millinder eingespielten Ellington-Komposition „(In My) Solitude“ konnte der Rang #8 der Hitparade erreicht werden. Allerdings schafften nachfolgende 78er wie „Dancing Dogs“ (#15), „Truckin’“ (#11), „Dinah Lou“ (#11), „Ride, Red, Ride“ (#9), „Merry Go-Round“ (#15) diese Platzierung nicht mehr. Ihre letzten Hits für Columbia waren ein weiteres Ellington-Stück („In a Sentimental Mood“) und im November 1936 Will Hudsons „Mr. Ghost Goes to Town“, eine Anspielung auf den damals populären Frank-Capra-Film Mr. Deeds Goes To Town.
Nach zwei Jahren verließen sie Columbia und wechselten zu dem kleinen Variety-Label, das gerade von Irving Mills gegründet worden war. Ihre erste Schallplatte hier war „Jungle Madness“ / „Blue Rhythm Fantasy“, aufgenommen am 11. Februar 1937. Aus dieser ersten Session stammte auch die nächste Single, tituliert als Lucky Millinder & Mills Blue Rhythm Band. Letzte Aufnahmesession hier war am 1. Juli 1937.
Die Band nahm insgesamt 150 Plattenseiten auf, doch durch das Fehlen regulärer Solisten gelang es der Formation nie, eine wirklich klare Identität und personelle Konsistenz als Jazzband zu entwickeln.
Im Jahr 1938 löste sich die Gruppe auf. Millinder übernahm zunächst die Band von Bill Doggett, bis er 1940 sein eigenes Orchester gründete.
Diskografie (in Klammern Aufnahmedatum)
Columbia
Out Of Dream / Let’s Have A Jubilee (Columbia 2963-D), 4. Oktober 1934
Solitude / Keep the Rhythm Going (Columbia 2994-D), 5. Dezember 1934
Spitfire / Back Beats (Columbia 3020-D), 25. Januar 1935
Dancing Dogs / Brown Sugar Mine (Columbia 3044-D), 5. Dezember 1934 / 25. Januar 1935
Harlem Heat / There’s Rhythm in Harlem (Columbia 3071-D), 2. / 9. Juli 1935
Truckin’ / Cotton (Columbia 3078-D), 1. August 1935
Dinah Lou / Waiting in the Garden (Columbia 3083-D), 1. August 1935
Ride, Red, Ride / Congo Caravan (Columbia 3087-D), 19. Dezember 1934 / 9. Juli 1935
Broken Dreams of You / Yes! Yes! (Columbia 3111-D), 20. Dezember 1935
Merry-Go-Round / Until the Real Thing Comes Along (Columbia 3147-D), 11. August 1936
In a Sentimental Mood / Carry Me Back to Green Pastures (Columbia 3148-D), 11. August 1936
Barrelhouse / Balloonacy (Columbia 3156-D), 15. Oktober 1936
The Moon Is Grinning at Me / Showboat Shuffle (Columbia 3157-D), 15. Oktober 1936
Mr. Ghost Goes to Town / Algiers Stomp (Columbia 3158-D), 20. November 1936
Callin’ Your Bluff / Big John’s Special (Columbia 3162-D), 20. November 1936
Variety
Jungle Madness / Blue Rhythm Fantasy, (Variety 503), 11. Februar 1937
Prelude To A Stomp / Rhythm Jam (Variety 546), 11. Februar 1937
The Image of You / Lucky Swing (Variety 604), 1. Juli 1937 / 28. April 1937
Medley: Camp Meeting Jamboree / When Irish Eyes Are Smiling (Variety 624), 1. Juli 1937
Let’s Get Together / Jackpot (Variety 634), 28. April 1937 / 1. Juli 1937