В начале 1923 г. Эллингтон вместе со своими друзьями-музыкантами появился в Гарлеме. Им хотелось попробовать свои силы в городе, где было много джазовых музыкантов. Вначале молодым джазменам не очень-то везло, Нью-Йорк было трудно покорить сразу. Были неудачные попытки работы с певцом из водевиля, иногда музыканты подрабатывали в бильярдных, чтобы раздобыть хоть какие-то средства на пропитание, однако не упускали случая поучиться, послушать мастеров страйда, и Дюк Эллингтон однажды попробовал себя в дуэлях с местными страйд-пианистами.
Музыканты все время были в поисках работы, теперь в состав «Washingtonians» («Вашингтонцы» — так музыканты себя назвали) входило шесть человек, и руководил ими Дюк Эллингтон. Именно в эту пору игра ансамбля начинает приобретать новые черты и оттенки. В музыке Эллингтона отразилось все: рэгтайм, услышанный еще в столице, более сложный гарлемский страйд и пропитанный блюзом новоорлеанский стиль Сиднея Беше и Луиса Армстронга. После того, как Эллингтон услышал оркестр Кинга Оливера, с «грязным» (dirty tones) звучанием духовых инструментов, перенесенными в инструментальный джаз из негритянского фольклорного («речевого») пения, он понял, как должен звучать его оркестр: кларнет, труба должны были звучать ярче, ритм исполнения произведения должен быть более четким. Успех не заставил себя долго ждать. К 1924 г. Дюка Эллингтона уже знали в Нью-Йорке. Его ансамбль записывали на пластинки, а музыкальные издательства покупали сочиненные композитором произведения. Но Эллингтон все равно был недоволен: несколько сезонов в «Kentucky Club» были не совсем успешными. Свое недовольство он как-то высказал другу — бродвейскому дирижеру, который советовал Дюку поучиться в консерватории. Но Эллингтон отказался, т.к. посчитал, что это будет пустая трата времени: в консерваториях в ту пору не учили тому, что он хотел исполнять. Тогда мудрый друг Эллингтона, а также один из выдающихся гарлемских страйд-пианистов по имени Уилли «Лев» Смит посоветовали следовать своей интуиции. И Дюк Эллингтон после этого разговора был всегда только самим собой.
Маэстро не терял оптимизма, подстрекаемый своим менеджером Ирвингом Миллсом, который понимал, какое сокровище в его руках. Дюк строил планы на будущее, реализовать которые вскоре стало возможно. В 1927 г. прошел слух, что самому престижному клубу в Гарлеме «Cotton Club» требуется совершенно новый оркестр. Это было большое заведение с залом на пятьсот мест для гангстеров и белых, у которых водились деньги.
Хозяином заведения был известный нью-йоркский мафиози. Однако в историю это заведение вошло не гангстерскими разборками, а множеством музыкально-популярных ревю. Два десятка «герлз» участвовали в шоу, музыку для которых писали знаменитые авторы: Джимми МакХью Дороти Филдс, Гарольд Арлен. По воскресеньям в клуб приходили бродвейские звезды и другие знаменитые артисты. И хотя клуб посещали в основном белые, выступали в клубе черные артисты. Об этом заведении мечтали все черные музыканты. Заманчивым для них было и то, что представления из «Cotton Club» транслировались по радио, а это, несомненно, способствовало широкой известности и популярности оркестров. (В конце XX в. режиссер Фрэнсис Форд Коппола снимет фильм «Клуб Коттон», который будет состоять из смеси жанров, популярных в американском кино: гангстерской тематики, мелодрамы и мюзикла. Фильм Копполы — о временах «сухого закона» и эпохе джаза, сопровождаемый чудесной музыкой Дюка Эллингтона.)
Начав работать в клубе, Эллингтон сразу же почувствовал, что это именно то место, которое он искал. Экзотическая атмосфера заведения потребовала от Дюка формирования собственного стиля, который получит название «стиль джунглей» (англ. jungle style). Имитация звуков джунглей создавалась в первую очередь исполнителями на медных духовых инструментах (трубач Баббер Майли и тромбонист Джо «Трики Сэм» Нэнтон) с помощью сурдинных граул- и уа-уа-эффектов. Затем в оркестр Дюка Эллингтона пришли те люди, которым позднее будет суждено стать великими солистами, импровизаторами: саксофонист Джонни Ходжес (1906—1970), кларнетист Барни Бигард (1906—1980), трубач Кути Уильямс (1908—1985), тромбонист пуэрториканец Хуан Тизол (1900—1984), барабанщик Сонни Грир (1885—1982).