Early in 1923, Henderson formed his own band with some of the musicians he knew through his studio work, including tenor-saxophone player Coleman Hawkins and alto saxophonist Don Redman. At this point, the band’s repertoire consisted mainly of bland, stock arrangements of show tunes and other popular music; while the recordings made money, there was nothing musically noteworthy about them. During the summer of 1923, the Club Alabam, a cellar spot situated beneath the Nora Bays Theater on West 44th Street, was looking for a house band to entertain the after-theater crowd. Henderson auditioned his band and was offered the position. Appearing under the name the Fletcher Henderson Orchestra, what started primarily as a studio band suddenly found itself performing nightly in the heart of Manhattan’s theater district.

Don Redman seized the opportunity to experiment with a working band and began to write the ensemble’s arrangements. Retaining the New Orleans style rhythm section of banjo, drums, piano and tuba, Redman expanded the ensemble to include full brass and reed sections, each of which was divided further into high and low sounding instruments. In performance, the melody was split between the brass and reed sections, often switching rapidly from one section to the next to create musical nuance and variation in tone color. One by one, the ensemble’s stock arrangements fell into disuse in favor of Redman’s more innovative ones. Redman’s increasingly complex arrangements for the big band, however, could not compensate for the Fletcher Henderson Orchestra’s one fatal flaw: None of the band members really knew how to improvise. This weakness became all the more apparent when the first King Oliver recordings featuring Louis Armstrong hit New York in 1923.