В «Коттон-клаб» время от времени приглашались оркестры Арманда Дж. Пайрона, креола из Нового Орлеана, прежде работавшего в танцзале «Роузленд», и «Хэппи» Роуна, популярного гарлемского бэнд-лидера. Но к 1926 году там выступал уже ансамбль «Миссурианз» под управлением Энди Прира. Дэн Хили рассказывает: «Самым главным был темп, темп и еще раз темп. Шоу обычно строились как набор составляющих элементов, таких, как оркестр, эксцентрический танцовщик, комедийный актер — тот, кто работал у нас и одновременно являлся звездой. Шоу продолжалось полтора, иногда два часа. Действие прерывалось выступлениями хороших вокалистов, таких, как Ада Уорд, Этел Уотерс. И всегда в программу входил особый номер — песня только для совершеннолетних в исполнении, например, Лейты Хилл». (Некоторые из этих вещей написал Арлен, в том числе «Pool Room Papa» и «My Military Man», но своего имени он под ними не ставил.) А по воскресеньям знаменитости шоу-бизнеса, оказавшиеся на представлении, тоже должны были выйти на эстраду со своим номером.
Успех превзошел все ожидания, но затем, в 1927 году, скоропостижно скончался Энди Прир, и владельцы клуба, по-видимому, воспользовались его смертью, чтобы избавиться от «Миссурианз». Позже ансамбль возглавил Кэб Кэллоуэй. Освободившееся в клубе место предложили Кингу Оливеру, выступавшему в танцзале «Савой», но Оливер, руководитель одного из известнейших негритянских оркестров, посчитал, что для состава в десять человек предложенная сумма мала. Тут-то и подоспели «Вашингтонцы».
История о том, как Эллингтон получил работу в «Коттон-клаб», рассказывалась неоднократно многими людьми и имеет множество различных версий. Полдюжины претендентов утверждают, что именно они предложили кандидатуру Дюка Старку и Гарри Блоку. Один из предъявлявших права на этот приоритет — Джимми Макхью, штатный автор Миллса, несомненно знакомый с коллективом Эллингтона. Дюк, во всяком случае, не возражал против заявлений Макхью.
Осенью 1927 года Дюк не работал в «Кентукки-клаб», а довольствовался тем, что удавалось подыскать. Ансамбль выступал в театре «Гибсон Стандард» в Филадельфии, когда им пришло приглашение явиться в полдень на прослушивание в «Коттон-клаб». Однако по условиям требовался состав из десяти человек. Пока Дюк набрал недостающих исполнителей и прибыл в Нью-Йорк, было уже два или три часа дня. К счастью для Эллингтона, опоздал и сам Гарри Блок. Прослушивание состоялось, ансамбль понравился и получил приглашение на работу. Жалованье составляло восемьсот долларов в неделю — сумма даже по тем временам небольшая, но «Коттон-клаб» считался престижным местом, что позволяло надеяться на большую в сравнении с «Кентукки-клаб» стабильность положения. Так что Дюк и Миллс ухватились за представившуюся возможность.
Оставалась последняя помеха. Ансамбль все еще был связан контрактом с театром. Как гласит многократно пересказывавшаяся история, кто-то из парней Мэддена связался с филадельфийским гангстером по имени Бу Бу Хофф. Хофф послал в театр Янки Шварца. Джазовое предание сохранило слова Шварца, адресованные театральному управляющему: «Будь добр. Или будешь мертв». Менеджер предпочел первое и разорвал договор.
Во всяком случае, так говорят. Первый выход ансамбля состоялся 4 декабря 1927 года. В истории джаза это одно из самых знаменательных событий, но в тот день об успехе не приходилось и мечтать. Музыканты практически не умели читать ноты, репетиций было явно недостаточно, а в состав коллектива только что вошли временные исполнители, и среди них скрипач Эллсворт Рейнолдс, который пробыл в ансамбле всего месяц. Нед Уильямс, вскоре ставший у Эллингтона агентом по рекламе, присутствовал на выступлении: «Не могу сказать, что Эллингтон со своими ребятами произвел на меня тогда сильное впечатление. Им еще, безусловно, не хватало вкуса и блеска, которые появятся позже».
Перед Эллингтоном тотчас же возникла необходимость стабилизации состава и доведения числа участников до оговоренных в контракте десяти человек. Для ансамбля, полагавшегося в своей работе главным образом не на нотную запись, а на аранжировки, которые музыканты держали в голове, постоянный состав исполнителей, способных играть по памяти, представлялся насущнейшей потребностью. В последующие два года Эллингтон вместе с ветеранами, составлявшими ядро коллектива, — Карни, Нэнтоном, Гриром, Бро и Гаем — создали превосходный оркестр, которому суждено было выпустить целый ряд лучших джазовых грамзаписей и сделать Дюка богатым и знаменитым.
Первым из вновь прибывших оказался новоорлеанский корнетист Барни Бигард. Он родился в 1906 году в типичной семье темнокожих креолов, где в домашнем кругу говорили по-французски. Как и многие темнокожие креолы, Бигард имел среди родни музыкантов и рос в атмосфере, пропитанной музыкой. Однако в данном случае это были не блюзы и реги, что соответствовало бы сложившимся в негритянской среде традициям, а «узаконенная» в приличном обществе музыка в классическом европейском стиле. Бигард выучился фотогравированию и сворачиванию сигар — специальностям, считавшимся у темнокожих креолов престижными, и попутно брал уроки игры на кларнете у легендарного новоорлеанского педагога Лоренцо Тио-младшего. «Лоренцо Тио и его дядя обучили меня практически всем основам игры на кларнете, — вспоминал Барни. — В их семье играли все: прадед, дед, дядя, племянник… Глубокий, чистый тон, который так нравился Дюку, составлял качественную особенность новоорлеанского исполнения, и многие кларнетисты были обязаны этим своим умением семейству Тио и Альфонсу Пику». (Род Тио не принадлежал к креолам, а происходил из Мексики.) Бигард признавался также, что многие приемы он «стянул» у Джимми Нуна, считавшегося лучшим кларнетистом новоорлеанской школы.
Креолы из Нового Орлеана предпочитали кларнеты старого образца, сделанные по системе Алберта, в отличие от более усовершенствованных системы Бёма с несколько иным расположением клапанов, что облегчало игру в быстром темпе. И подобная верность традиции не лишена была некоторых оснований. По заключению кларнетиста Боба Спаркмена, занимавшегося этой проблемой, старые кларнеты, как и многие духовые инструменты тех лет, имели большую мензуру. Это обеспечивало большую насыщенность звука, столь необходимую для выступлений на открытом воздухе, которые в то время носили преобладающий характер. В целом, духовые инструменты с большей мензурой обладают более полным и сочным звучанием в низком регистре, тогда как в высоком несут некоторые потери. Креолы использовали преимущества системы Алберта для исполнения продолжительных быстрых пассажей, и Дюк находил блестящее применение особому умению Бигарда играть в низком регистре.
Бигард еще подростком выступал в Новом Орлеане и некоторое время работал в знаменитом кабаре Тома Андерсона в Сторивилле, где в давние дни играли многие ведущие негритянские джазмены. В 1924 году Кинг Оливер перетянул Бигарда на Север. Барни оставался в его оркестре до 1927 года, то есть до тех пор, пока Оливера не начала мучить поврежденная губа и не возникли трудности с ангажементами. Затем Бигард оказался в ансамбле Луиса Расселла, выступавшем в известном гарлемском ночном клубе «Нест», который обслуживал смешанную публику: