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