Кути пробыл у Шилдса несколько лет, а затем вместе с Холлом перешел в ансамбль под управлением Алонсо Росса в клуб «Делла Робиа». Коллектив Росса действовал на кооперативных началах и являлся крупнейшим негритянским оркестром во Флориде. Время от времени его концерты транслировались по радио, и в 1928 году передачу услышал некто, связанный с бруклинским дансингом «Роузмонд Боллрум». Последовало приглашение, и оркестр на две недели отправился на север. После гастролей, не получив новых предложений, музыканты вернулись домой. Но Кути и Эд Холл, ошеломленные возможностями, открывающимися перед джазменами в Нью-Йорке, решили остаться. Несколько недель они мотались по Бруклину, питаясь супом по пятнадцать центов за миску, пока им не рассказали о Манхэттене и гарлемском клубе «Бэндбокс», где, как и у Мексико, регулярно проводились соревнования музыкантов. Кути отправился туда в ночь трубачей. Кто-то услышал его и привел Чика Уэбба, впоследствии ставшего руководителем одного из лучших свинговых оркестров 30-х годов, а пока стоявшего в начале пути. Уильямс так понравился Уэббу, что он предложил ему жить в своем доме и взял на работу, положив жалованье тридцать пять долларов в неделю — для Кути «большие деньги». Однако у Уэбба возникли какие-то недоразумения с профсоюзом, и Кути пришлось уйти. В начале 1929 года он устроился в оркестр Флетчера Хендерсона, находившегося в зените славы, но пробыл там лишь несколько недель, затем ненадолго вернулся к Уэббу и вновь перебрался к Хендерсону. Однако и на сей раз связь оказалась непродолжительной: очень скоро Кути получил предложение от Дюка.
Дюк, как мы видели, всегда с большим терпением относился к неподобающим поступкам некоторых своих музыкантов, считая, что раскованные, полагающиеся на интуицию исполнители смогут создавать более «свободную и естественную» музыку. Он даже в нотной записи иногда ставил пометку «небрежно». При этом, как ни парадоксально, его викторианское воспитание и стремление к аристократизму обусловило тот факт, что его собственный стиль поведения больше походил на стиль поведения белых, нежели на манеру менее закомплексованных, по общему мнению, негров, которые в те времена служили идеалом для интеллектуальной части общества.
Однако Баббер Майли зашел слишком далеко. После работы он пускался в путешествие по Гарлему, навещал женщин и друзей, наведывался в другие клубы. Иногда странствия затягивались до следующего вечера, так что пора уже было снова выходить на работу. Он являлся пьяным и нечесаным, в несвежей рубашке с пятнами от еды и напитков, присыпанными тальком, который он специально для этой цели носил в футляре для трубы. Ему разрешалось вздремнуть между отделениями, чтобы таким образом хоть как-то дотянуть до конца шоу.
Очень часто он вообще не появлялся в клубе. Кути рассказывал: «Причина, почему [Дюк] уволил Баббера Майли, вот какая: каждый раз, когда какая-нибудь важная шишка приходила послушать ансамбль, Баббера Майли не было на месте, а на нем держалось все выступление». Майли не явился и на очень ответственную запись «Black and Tan Fantasy», и его заменял Джаббо Смит. (По иронии судьбы через несколько месяцев Кути пришлось в аналогичной ситуации играть вместо Джаббо, чтобы режиссер не понял, что произошла замена.) Наконец однажды Баббер не явился на работу, когда на прослушивании в «Коттон-клаб» присутствовал очень влиятельный агент, занимавшийся ангажированием оркестров. Подписать контракт не удалось, и в начале 1929 года Дюк уволил Баббера. Что говорилось при объяснении, нам неизвестно, но Майли, несомненно, получил отставку, а не намек на то, что пора уйти по собственному желанию, как впоследствии часто рассказывали. Тогда-то Джонни Ходжес, который некоторое время играл с Кути у Чика Уэбба, и сказал Дюку: «А что, если пригласить Кути?»
Почему Кути согласился на предложение, неясно. Коллектив Хендерсона являлся ведущим негритянским оркестром в стране, и понятно, что платили там больше, чем у Дюка. Но Кути только заметил: «У Флетчера был самый лучший оркестр, но Дюк рвался вперед». Решение Уильямса оказалось мудрым. Коллективу Хендерсона предстояло пережить трудные времена, и к моменту окончания преобразований (через год или около того) оркестр Эллингтона добился первенства.