The Cab Calloway Orchestra, based at the exclusive Cotton Club in Harlem, was, for more than a decade, one of the most important jazz bands in America. Different lineups featured the best available established musicians.

In 1930, Cab Calloway was hired to replace Duke Ellington at the Cotton Club, and recorded for Brunswick and the ARC dime store labels (Banner, Cameo, Conqueror, Perfect, Melotone, Banner, Oriole, etc.) from 1930–1932. In 1932, he signed with Victor for a year, but he was back on Brunswick in late 1934 through 1936, when he signed with manager Irving Mills's short-lived Variety in 1937, and stayed with Mills when the label collapsed and the sessions were continued on Vocalion through 1939, and then OKeh Records through 1942.

When the Cotton Club closed in 1940, Calloway and his band went on a tour of the United States.

In 1941 Calloway fired Dizzy Gillespie from his orchestra after an onstage fracas. Calloway wrongly accused Gillespie of throwing a spitball; in the ensuing altercation Gillespie stabbed Calloway in the leg with a small knife.

The band broke up in the late 1940s.