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