В последующие годы состав оркестра менялся часто, нов нем неизменно присутствовали выдающиеся музыканты — Рекс Стюарт, Бобби Старке, Ирвинг Маус Рэндольф (труба), Бенни Мортон, Хиджинботем, Сэнди Уильямс, Дики Уэллс (тромбон), Бенни Картер, Расселл Прокоп, Хилтон Джефферсон (альт-саксофон), Бен Уэбстер, Чу Берри (тенор-саксофон), Джон Керби, Элмер Джеймс (контрабас), Уолтер Джонсон, Сидней Кэтлетт (ударные).
С Хендерсоном работали два блестящих джазовых аранжировщика: Дон Редмен и Бенни Картер, который в 1929-1930 годах в огромной степени способствовал успеху оркестра. Интересно отметить, что сам Хендерсон тоже был известным аранжировщиком, но для собственного коллектива стал писать аранжировки только с 1934 года.
До 1937 года ансамбль Флетчера Хендерсона принадлежал к числу лучших, затем отошел на второй план.
В 1925-1930 годах в Гарлеме пользовались популярностью и другие оркестры: Чарли Джонсона (в его составе играли трубач Сидней Депэрис, ударник Джордж Стэффорд и, недолго, Джимми Херрисон и Бенни Картер) и Льюиса Расселла, в игре которого преобладал нью-орлеанский стиль благодаря замечательным музыкантам-уроженцам этого города — Элберту Николасу (кларнет), Полу Барбарену (ударные) и изумительному контрабасисту Попсу Фостеру (род. в 1892 г. под Нью-Орлеаном). Игра Фостера произвела на музыкантов столь сильное впечатление, что почти все оркестры сменили тубу на контрабас. Исполнение трубача Генри Аллена, тоже уроженца Луизианы, было лишено уравновешенности, четкой и стабильной ритмичности, свойственной трубачам нью-орлеанского стиля. Он играл лихорадочно, нервно. Одного из крупнейших джазовых тромбонистов, поражавшего слушателя энергичной силой, эмоциональным накалом и виртуозностью, оркестр имел в лице Дж. К. Хиджинботема (род. в 1906 г. в Атланте, шт. Джорджия). Самые трудные пассажи удавались ему с потрясающей легкостью, и Хендерсон в шутку говорил, что он, наверно, родился с тромбоном во рту. Расцвет оркестра Льюиса Расселла приходится на 1928-1932 годы.
Оркестр Mc Kinney's Cotton Pickers играл в Гарлеме эпизодически, потому что был театральным коллективом и много ездил в турне, кочуя из одного мюзик-холла в другой (то, что в США называется vaudeville circuits). На уровень лучших Mc Kinney's Cotton Pickers вышел в 1927 году, когда его музыкальным руководителем стал специально пришедший сюда от Хендерсона Дон Редмен. В числе музыкантов оркестра были трубачи Джо Смит, Сидней Депэрис и Рекс Стюарт, тенор-саксофонист Принс Робинсон, певец Джордж Томас и некоторое время Бенни Картер.