В 1935 году, когда семья переехала в Филадельфию, Гиллеспи уже был столь умелым музыкантом, что почти сразу нашел работу в коллективе Фрэнка Файрфакса, в котором провел полтора года. В 1937 году он перебрался в Нью-Йорк и стал завсегдатаем одного из самых известных гарлемских танцевальных залов, Savoy Ballroom. Здесь он познакомился с Тедди Хиллом, в коллективе которого прежде играл кумир Гиллеспи трубач Рой Элдридж; Гиллеспи учился музицировать, слушая его по радио и копируя его скоростные партии. Хиллу после ухода Элдриджа был нужен трубач, который умел бы играть сходным образом, и Гиллеспи отлично ему подошел[1235]. Спустя два года он перешел в оркестр Кэба Кэллоуэя, из которого был уволен в 1941 году после довольно шумной и характерной для темперамента Гиллеспи истории. Кэллоуэй вообще с подозрением относился к Гиллеспи, который к этому времени, познакомившись с Монком и часто посещая «Минтон», уже начал разрабатывать гармонический язык бибопа; сам Гиллеспи, в свою очередь, был недоволен Кэбом за то, что тот, по его мнению, недостаточно его ценил: по этим причинам они часто ссорились. На одном из концертов второй трубач оркестра, Джона Джонс, кинул бумажный шарик в другого музыканта. Кэллоуэй стоял за кулисами, и ему показалось, что это сделал Гиллеспи; после концерта он обвинил того в недолжном поведении, завязалась ссора, и взбешенный Гиллеспи пошел на Кэллоуэя с ножом; их тут же кинулись разнимать, однако Гиллеспи удалось ударить Кэллоуэя лезвием в бедро[1236]. Позже они помирились, но больше Гиллеспи в оркестре не играл.

В 1939 году он познакомился с афрокубинским трубачом Марио Бауза, который, собственно, и уговорил Кэллоуэя нанять его: с этого момента начинается увлечение Гиллеспи латино-джазом, которое будет продолжаться всю его жизнь. Позже, в 1947 году, Бауза представил Гиллеспи своего земляка, перкуссиониста-виртуоза Чано Посо, который затем играл в коллективе Гиллеспи, придавая музыке последнего тот самый «испанский оттенок», о котором когда-то говорил Джелли Ролл Мортон[1237]. Спустя год Посо был застрелен в баре – судя по всему, уличным торговцем наркотиками, с которым он поскандалил; Гиллеспи, всегда требовавший от участников своих коллективов дисциплины, после его смерти сделался еще более строгим лидером и безжалостно увольнял музыкантов, которых он подозревал в употреблении наркотиков[1238].

Гиллеспи не попал в армию и, соответственно, на фронт, поскольку не раз во всеуслышание заявлял, что может начать стрелять в белых американских солдат, спутав их с немцами; он, таким образом, отредактировал и вернул белым их же собственный расистский стереотип о том, что все черные «на одно лицо»[1239]. В то время подобные высказывания могли обернуться серьезными неприятностями (даже сейчас их бы не оставили без внимания), но Гиллеспи важно было продемонстрировать «позу», тот самый attitude, который будет позже столь важен для артистов хип-хопьа, и он пошел на риск. Он был большим модником, носил берет, козлиную бородку и очки без диоптрий, и нью-йоркские хипстеры и битники подражали ему как в одежде, так и в ленивой, расслабленной манере говорить[1240]. Когда он сфотографировался в расстегнутой рубашке, среди хипстеров Нью-Йорка сразу стало модным ходить в расстегнутых рубашках. В 1947 году критик Гилберт Маккин писал в журнале Esquire: