In June 1929, Andy Kirk and the Twelve Clouds of Joy, one of the leading territorial bands, arrived in Kansas City for an extended engagement at the Pla-Mor Ballroom on Main Street, just south of Linwood Boulevard. Finding ample work in ballrooms, the Clouds of Joy moved their headquarters from Oklahoma to Kansas City.
Originally from Kentucky, Andrew Kirk grew up in Denver. In grade school Kirk studied music with Wilberforce Whiteman, father of band leader Paul Whiteman. Kirk initially picked up the tenor saxophone, but soon switched to tuba and baritone saxophone. During World War I, he worked as a mailman while moonlighting with the George Morrison Orchestra. Kirk soon left the civil service to become a full-time member of the Morrison band.
In 1926, Kirk moved to Chicago. Unable to find steady work, Kirk joined T. Holder and the Dark Clouds of Joy in Dallas, Texas. The newly-formed Holder band played the Ozarks, a rough-and-ready roadhouse on the outskirts of Dallas. In 1927, the Holder band relocated to Oklahoma, where they alternated between ballrooms in Tulsa and Oklahoma City. Saxophonist John Williams joined the band in Oklahoma City. Williams' child bride, Mary Lou, soon joined her husband. A gifted and powerful pianist, Mary Lou aspired to join the group, but band members not wanting a woman in the group dashed her hopes.
Kirk took over leadership of the Dark Clouds of Joy during the 1928 Christmas season, when Holder disappeared with the band's payroll. Kirk disliked the racial implications of the Dark Clouds of Joy, so he shortened the band's name to the Clouds of Joy. George E. Lee gave the Kirk band entre to Kansas City. While passing through Oklahoma City, Lee stopped in to check out the Clouds of Joy. Impressed by the band, Lee recommended the Clouds of Joy to the management of the Pla-Mor.
After moving to Kansas City, the Clouds of Joy switched their union affiliation from the white Musicians Union Local 94 in Tulsa to Local 627. In November 1929, the Kirk band auditioned for the Brunswick label. When the band's pianist failed to show, Mary Lou Williams eased into the piano bench. The band won the audition, but lacked enough original material to carry the session. Kirk recruited Mary Lou Williams to craft new compositions for the sessions. Her composition "Mess-A-Stomp" exceeded the range of the band. Although Williams made the greatest contribution to the session, band members still denied her a slot in the band.
In early 1930, the Clouds of Joy filled in for the Fletcher Henderson band at the Roseland Ballroom in New York. The band remained in the East, touring New York and New England. Mary Lou Williams joined the band as a regular member during an engagement in Philadelphia. After Blanche Calloway attempted to take over leadership of the band, the Clouds of Joy returned to Kansas City. With the Great Depression shutting ballrooms and theaters across the country, the Clouds of Joy stayed close to Kansas City. In 1936, the Clouds of Joy became established nationally on the success of the hit recording "Until the Real Thing Comes Along," sung by Pha Terrell.