К 1957 году Хейден уже созрел для того, чтобы играть новую музыку. И вот однажды пианист Пол Блей рассказал Чарли о саксофонисте, которого почти всегда в клубах просят прекратить играть уже после нескольких тактов, его инструмент сделан из белой пластмассы и звучит вызывающе резко. "Его альт-саксофон походил на большую игрушку, но этот парень своей игрой перевернул весь мой ум. Все встало на свои места, как будто кто-то указал пальцем: «Вот так и должно быть». Я встретил Орнетта Коулмена в следующее воскресенье и сказал ему: «Послушай, парень, мне действительно нравится, как ты играешь. Я думаю, у нас появится шанс, если мы сможем сделать что-то вместе». Он ответил: «Отлично, давай попробуем». Мы поехали к нему домой. Когда дверь открылась, то оказалось, что ступать пришлось не на половик, а на... музыку — листки с нотами были разбросаны везде — на полу, на кровати, на комоде... Я распаковал контрабас, а Орнетт подобрал с пола один листок, поставил его на пюпитр и сказал: «Давай сыграем эту тему. Я здесь выписал все гармонии, но тебе необязательно следовать нотам. Играй как слышишь»". Это была та музыка, о которой Чарли мечтал.

Необычные мелодии и созвучия заставляли думать и подстегивали воображение... Коулмену тоже очень не хватало коллеги-единомышленника. В результате родился квартет Коулмен — Черри — Хейден -Хиггинс, через два года открывший серию своих исторических записей на фирме "Atlantic". Альбомы "Change Of The Century" и „The Shape Of Jazz To Come" стали вершиной творчества квартета, объединив в себе композиторский талант Коулмена, импровизационные и одновременно мелодические способности Хейдена, свободный и яркий стиль Хиггинса и пронзительно-лирический тон "карманной" трубы Дона Черри. Одна из последующих работ, "Free Jazz", записанная сразу двумя квартетами, играющими каждый свою импровизацию (к основному составу присоединились Эрик Долфи, Фредди Хаббард, Скотт Ла Фаро и Эд Блэкуэлл), дала имя новой музыке и стала ее манифестом. Чарли научился у Орнетта Коулмена принципам свободной импровизации, когда определенные мелодии и гармонии служат только источником вдохновения, но не держат музыканта жестко "при себе". Виртуозность как таковая здесь была необязательна, главное заключалось в соединении свободных гармонических и мелодических схем с ярким лиризмом, который всегда был свойственен контрабасисту. Эта особенность и стала ключом к успеху: все проекты, в которых в дальнейшем участвовал Чарли Хейден, отличает несомненная доля романтизма — он смягчает внешнюю жесткость и колючесть необычных звуковых сочетаний и интервалов нового джаза. Не зря в одном из своих уже поздних интервью музыкант говорит: „Я хочу, чтобы мои слушатели были затронуты чистой красотой музыки, чтобы они осознавали эту красоту просто как часть своей жизни, часть всего мира и чтобы они запомнили важность романтических ощущений".

Конец шестидесятых. Чарли с женой Рут живет в Нью-Йорке, часто выступает с Тони Скоттом, Арчи Шеппом, входит в состав квартета с Кейтом Джарреттом, Полом Мотианом и Деви Редманом (они вместе за десять лет записали дюжину альбомов на разных лейблах), продолжает сотрудничество с Коулменом и, что самое интересное, исполняет с одинаковым интересом и успехом любой джаз, независимо от направления. Один из величайших свинговых трубачей Рой Элдридж, на дух не переносивший современный свободный стиль, однажды спросил Хейдепа после совместного концерта в клубе "Half Note": „Как тебе вообще удается играть и с Орнеттом, и со мной?". Рой получил простой и совершенно неожиданный ответ: "Легко. Вы оба прекрасные музыканты и делаете одинаково великолепный джаз. Разница совсем невелика". Семья Хейдена увеличивалась, родился сын Джошуа, это требовало новых расходов, а музыкант был вовсе не богат. Впервые ему пришлось идти в кабалу на студию звукозаписи, работать сессионным музыкантом, делать джинглы... Он чувствовал себя буквально больным, осознавал, что расходует себя по пустякам и делает то, что не любит и во что не верит. Но ему все же повезло, да и талант наконец сработал — собственные проекты стали приносить доходы, и больше, по его словам, он „никогда в жизни не брался за работу, к которой не лежала душа".

В 1969 году Чарли вместе с пианисткой и композитором Карлой Блэй организовал оркестр из 11 музыкантов под названием "Liberation Music Orchestra" ("Оркестр музыки освобождения"). Они много и с успехом гастролировали, а записи оркестра все как одна были отмечены всевозможными призами. Первый альбом получил французский эквивалент Грэмми ("Grand Prix Charles Cros"), a также был номинирован на саму премию Грэмми. Хейден был награжден также премией "Guggenheim Fellowship" за композицию. Два следующих альбома этого оркестра, "Ballad Of The Fallen" и "Dreem Keeper", признавались лучшими альбомами года по опросам критиков журнала "Даун-бит" в 1984 и 1991 годах, а последний еще и номинировался на Грэмми. Проект следует за проектом, фирмы звукозаписи одна за другой падают к ногам Хейдена. В 1976 году возникает группа "Old And New Dreams" ("Старые и новые мечты"), в которую кроме Чарли входят Дон Черри, Деви Редман и Эд Блэкуэлл. Дебютный альбом выходит на фирме "Black Saint", а затем на них обращает внимание лейбл "ЕСМ", который уже тогда приобретал славу эстетствующего и модернистского. "ЕСМ" выпустила много разных альбомов с участием Хейдена, как чисто джазовых, так и экспериментальных, например "Arbour Zena" с Яном Гарбареком, Кейтом Джарреттом и струнным оркестром.

Фактически это была уже просто современная камерная музыка, где джазовые приемы присутствовали только как элемент колористи-ки. Необычайно интересно следить за философско-раздумчивым напевным тоном Хейдена на теплом, неотстраненном фоне струнных и врывающихся время от времени страстных пассажей фортепьяно и саксофона. В то время подобная музыка считалась чем-то вроде чудачества заскучавших джазменов и была принята весьма неоднозначно, но сейчас, на фоне современных новоджазовых экспериментов, видно, что она просто опередила свое время. Последние три десятилетия в джазе прошли, если можно так выразиться, под знаком контрабаса Чарли Хейдена. Он 17 раз признавался лучшим басистом в опросах критиков Down Beat, много раз номинировался на Грэмми, его записи неоднократно признавались лучшими альбомами года, а его акустический "Quartet West" (Эрни Уотте — саксофон, Алан Бродбент — фортепиано, Лоренс Мэрсйбл — ударные) был принят и прессой, и слушателями с таким единодушным энтузиазмом, какого он сам не ожидал. Дело в том, что после многолетнего исполнения разнообразных музыкальных новшеств Хейден решил вернуться в 40-50-е годы — очень много вещей из репертуара нового квартета навеяны музыкой тех лет. Несколько альбомов "Quartet West" в девяностые годы становились неизменными хитами знаменитого лейбла "Verve".

В последние годы Хейден работает в почти противоположных музыкальных направлениях. Записи и концерты с Джо Ловано и Джоном Скофилдом продолжают авангардную линию, а "Quartet West" и дуэты с Кении Барроном и Патом Мэтини демонстрируют романтическую сторону его творчества. Ко всему прочему, он еще принимал участие в записи альбома современного академического английского композитора-минималиста Гэвина Брайарса. Много внимания он уделяет и преподаванию в джазовой студии Калифорнийского института искусств. Только очень смелый и уверенный в себе учитель может сказать своим ученикам: "...если вы хотите играть музыку одновременно на уровне свободы и на уровне красоты, то для этого вам нужно представить себе, что каждую ноту вы извлекаете из инструмента с риском для жизни... А еще абсолютно необходимо каждому открыть свою душу для звуков и не пользоваться чужими наработками. Ведь разные люди воспринимают одну и ту же мелодию по-разному, точно так же, как имеют разные отпечатки пальцев. Я только помогаю всем найти свои собственные звуки, свои гармонии... Не так важно, какая у вас техника, я говорю о духовной связи с процессом творчества...". Многие проблемы современного состояния джаза волнуют мастера, например, тот факт, что нынче большинство джазменов любят играть на предельных громкостях и джазовые концерты по своей звуковой мощности приближаются к рок-представлениям.

Хейден безжалостен и точен в своей оценке: „Люди хотят слышать мощное звучание, потому что это дает им ощущение собственной силы... Но при этом можно просто-напросто повредить свой слух. На моих курсах я учу тому, что музыкант обязательно должен слышать натуральное, естественное звучание своего инструмента во всех нюансах для того, чтобы найти свой саунд. Неважно, что это — вибрация трости в саксофоне, амбюшур трубача, движение смычка по струнам или фортепьянное туше — вы не сможете понять до конца свой инструмент, если он не будет звучать в меру громко и натурально. Очень важно почувствовать динамику инструмента, а для этого надо уметь играть тихо. Если сразу начать форсировать громкость, то вы никогда не поймете, что такое динамика звука. А ведь возможности человека управлять инструментом почти безграничны...". Сейчас Чарли Хейден живет на Западном побережье, в городе Санта-Моника, и его семья такая же музыкальная, какой была семья его родителей. Мало того что две из трех его дочерей играют на контрабасе, а одна — на виолончели, сын также избрал своим инструментом контрабас. Такое вот "басистое" семейство. Когда мастера спрашивают о планах, он отвечает незамысловато: "Я всегда поглощен мыслью о новой музыке. Ее форма не так важна — я собираюсь записать альбом танго, а также фламенко, но это будет все равно что-то новое, чего раньше еще не было...". Цель жизни этого человека — сыграть как можно больше хорошей музыки для как можно большего количества слушателей. И он верит, что от этого мир станет хоть немного лучше.