Уже в очень раннем возрасте Чарли брал уроки игры на фортепиано, но в 12 лет ему подарили саксофон строя до, нечто среднее между альтом и тенором, а позднее он освоил и всё остальное наследие Адольфа Сакса. В 1929 г. он уже играл в пароходном оркестре, с которым 22 раза пересёк океан, побывав в Европе и Южной Америке. Его фаворитами в те годы были Коулмен Хокинс (тенор) и Джонни Ходжес (альт), но особенно глубокое влияние на Барнета оказал Дюк Эллингтон, его музыка и оркестр. Свой первый значительный биг-бэнд в Нью-Йорке на регулярной основе Чарли сформировал ещё в 1933 г., и многие его аранжировки (которые тогда писали для него Эдди Сотер, Тутти Камарата, а позже — Билли Мэй) были построены по образцу работ Дюка. Барнет любил окружать себя вдохновенными, творческими музыкантами в независимости от их цвета кожи и был одним из очень немногих первых бэнд-лидеров, в оркестре которых играли негры. Так, с ним играли чёрные джазовые «звёзды» Трамми Янг, Пинатс Холленд, Оскар Петтифорд, Рой Элдридж, Кларк Терри, Чарли Шэйверс, пела Лина Хорн, и его оркестр был первым таким ансамблем, выступившим в гарлемском театре «Аполло» для негритянской публики. В дальнейшем из-за своего антирасизма Чарли даже имел неприятности с ангажементами в фешенебельных отелях, куда не пускали «черномазых», и его бэнд по той же причине не приглашали участвовать в коммерческих радиопередачах. Но он твёрдо придерживался своих принципов. Каждый свинговый, да и любой джаз-оркестр всегда стремится иметь какой-то свой сногсшибательный хит (коммерческий и музыкальный), и для Барнета это произошло в 1939 г., когда 17 июля на фирме «Victor/Bluebird» он записал буйную, неистовую версию темы Рэя Нобла «Cherokee», вскоре ставшую главной темой его биг-бэнда. С неё, между прочим, начался тогда интерес к джазу знаменитого впоследствии Уиллиса Коновера, который спустя тридцать пять лет рассказывал: «Первая из понравившихся мне джазовых записей была „Чероки“ в исполнении Чарли Барнета, что делало меня в глазах тех, чей вкус не пошёл дальше диксиленда, слишком модным. Это была первая пластинка, которая произвела на меня сильное впечатление, и я стал собирать другие похожие записи. Владелец музыкального магазина, бывший музыкант, однажды сказал мне: „Ты, видно, любишь джаз?“ — „Джаз? А что это такое?" — спросил я. „Это пластинки, которые ты собираешь, и музыка, которую ты передаёшь"».
Историки джаза считают годами расцвета оркестра Барнета 1939-1945, когда им было сделано большое количество удачных записей на «Bluebird», до 1942 г., включая «Pompton Turnpike», «Charleston Alley», «Wings Over Manhattan», «Redskin Rhumba» и в особенности запись его собственной пьесы «Skyliner» (уже на фирме «Decca», 1942-1946), ставшей ещё одним из величайших хитов его бэнда. А в 1949 г. Барнет собрал боповую группу первоклассных молодых музыкантов и записал с ними диск «Bebop Spoken Here», звучавший более чем современно, хотя в саксофонной игре самого лидера не произошло заметных стилистических изменений.
