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