В 1935 году Гиллеспи получил свой первый ангажемент в оркестр Ф. Фэйрфакса. Прозвище «Диззи» — ошеломляющий и в то же время ошеломленный — он получил в 17 лет, начав работать в Филадельфии.
Вскоре Диззи занял место Роя Элдриджа в оркестре Тэдди Хилла. Элд-ридж долго служил великолепным образцом и примером для Гиллеспи. С оркестром Тэдди Хилла летом 1937 года Гиллеспи впервые приехал в Европу. Хилл говорил «Несколько моих музыкантов угрожали покинуть opкестр, если я возьму с собой этого сумасшедшего. Но оказалось, что молодой „Диззи“ со своей эксцентричностью и постоянной способностью острить был самым надежным человеком в оркестре. Он скопил себе так много денег, что даже поощрял других брать у него взаймы, чтобы он по возвращении в Штаты имел бы с этого некоторый доход».
Диззи Гиллеспи добился успеха сразу же, как только начал играть иначе, чем другие. Один французский ударник писал тогда. «В оркестре Тедди Хилла есть очень молодой, весьма многообещающий трубач. Жаль, что ему не дают возможности сделать свои записи. Он вместе с тромбонистом Дики Уэллсом является самым талантливым музыкантом оркестра. Его зовут Диззи Гиллеспи».
В 1939 году он был приглашен в биг-бэнд К. Кэллоуэя. Здесь за короткий срок Гиллеспи проявил себя как солист, композитор и автор аранжировок.
«Именно работая у Кэллоуэя, я впервые встретился в Канзас-сити с Чарли Паркером, — продолжает Гиллеспи. — В то время я давал концерты вместе с приятелем, трубачом Бади Андерсеном. Как-то он уговорил меня послушать какого-то саксофониста, но я не проявлял особого интереса, так как слышал, как мне казалось, уже всех знаменитостей. Но когда я услышал Чарли Паркера, то был просто потрясен. Мы целый день играли вместе в одном из отелей.
Это было в конце 30-х годов. Чарли Паркер оказался настоящим творцом новой музыки. Он знал, как перейти от одного звука к другому, тонко чувствовал стиль. До этого я мыслил преимущественно категориями ритма и гармонии… Трудно объяснить словами, как рождается его музыка. Для меня необходим был именно такой импульс, чтобы я смог и сам вполне раскрыться. Это не плагиат: каждый из нас вкладывал в исполнение то, что имел».
Так Диззи Гиллеспи пришел к тому новому стилю исполнения, который прославил его имя. Кэб Кэллоуэй, однако, не желал терпеть в своем оркестре такого стиля игры на трубе, в котором играл Гиллеспи. Ему также не нравились всегдашние проделки Диззи. Однажды в разгар выступления оркестра тот бросил в своего бэнд-лидера бумажный шарик. Как рассказывает контрабасист Милт Хинтон, «лишь в гардеробной Кэб увидел кровь на одежде и понял, что уже в следующий момент „Диззи“ пырнул его ножом». После этого они разошлись окончательно.
Диззи говорил: «Когда я рос, то все, что бы я хотел играть, было свингом. Рой Элдридж был моим идеалом — я пытался делать все, как он. Но я никогда не мог этого достигнуть, я совершенно сошел с ума, так как ничего подобного не получалось. Наконец я попытался играть иначе. Из этого получилось затем то, что теперь называют бопом».
Первая пластинка, которая ознаменовала рождение этого стиля, вышла в 1942 году; он играл с оркестром Лесса Хаита маленькую пьеску, называющуюся «Хвастун из Нью-Джерси». Но фразировка, динамический диапазон, гармоническая изобретательность, виртуозность исполнения тут были принципиально новыми для джаза. В следующие годы этот новый стиль совершенствовался и вскоре стал популярным среди музыкантов Америки. Басист Оскар Петифорд организовал тогда вместе с Гиллеспи первый оркестр «би-бопа», начавший выступать на 52-й улице в Нью-Йорке, которая в то время называлась «Свинг-стрит». За ним начали возникать новые и новые коллективы, и вскоре в полный голос заявили о себе лучшие представители нового стиля — выдающиеся негритянские музыканты.
Леонард Фезер: «У Диззи было множество безусловных почитателей на 52-й стрит, которые подражали ему даже в одежде, походке, его бородке, очкам и другим чисто внешним данным». «Диззи создал тогда то, что затем должно было распространиться на весь мир как „мода на би-боп“. Даже галантерейщики предлагали на выбор галстуки „би-боп“».
А Гиллеспи все больше входил в роль биг-бэндовского музыканта. После известного скандала с Кэллоуэем он играл у Бэнни Картера, Чарли Барнета, Лаки Миллиндера, Эрла Хайнса, затем Дюка Эллингтона и Билли Экстайна.
Билли Экстайн рассказывал: «Диззи — он как лиса. Это один из самых ловких парней, которых я знал. В музыкальном отношении он также знал наперед, что нужно делать. Все, что он слышал, он „наматывал на ус“, хотя можно было подумать, что это в одно его ухо входит, а в другое выудит. Но все входило в него и оставалось в нем. А позже, когда он придет юмой, то будет все время размышлять об этом».