Саксофон освоил самостоятельно, играл в школьном духовом оркестре (вместе с Девью Рэдменом и барабанщиком Чарльзом Моффетом), в 14 лет начал выступать с местными ритм-энд-блюзовыми группами, некоторое время аккомпанировал вокалисту Бит Джо Тернеру. В 1952-59 работал в Лос-Анджелесе лифтером и брал уроки музыки, в 1957 году вместе со своими друзьями — трубачом Доном Черри, барабанщиком Эдом Блэкуэллом и другими единомышленниками — начал экспериментировать, играл на пластиковом альт-саксофоне и строе С (как самоучка, вначале он неверно транспонировал), вводил в импровизационную музыку мелодическую непрерывность, ритмическую асимметрию, отказывался от привязанности к тональности и от куплетной формы. Первые записи — Something Else! (1958) и Tomorrow Is The Question (1959) — помог организовать Рэд Митчелл. Джон Льюис и Гантер Шуллер помогли квартету Коулмана (с Доном Черри, Эдом Блэкуэллом и Чарли Хэйденом) получить ангажемент в нью-йоркском клубе Five Spot (1959). В 1959-63 годах квартет записал семь альбомов, выступал на крупнейших американских фестивалях (в Ньюпорте и Монтерее), гастролировал в Европе.
В 1963-64 Коулман прекратил выступления и потратил более полутора лет на освоение трубы и скрипки. В 1965 организовал квартет (с Чарльзом Моффетом и Дэвидом Айзензоном), а в следующем году журнал Down Beat назвал его «музыкантом года». В середине 60-х годов написал музыку к нескольким кинофильмам, а в 1972 году записал с Лондонским симфоническим оркестром альбом Skies Of America, использовав свою новую так называемую гармологическую теорию (построение одинаковых интервалов у транспонирующих и нетранспонирующих инструментов). В 1973 году начал новые эксперименты, соединяя африканскую музыку и рок-ритмы и вводя в ансамбль электрогитару (группа Prime Time).
Деятельность Коулмана разделила джазовый мир на два лагеря — на тех, кто видел в нём мессию, и на тех, кто считал его шарлатаном. Темпераментные и свободные импровизации Коулмана были неповторимо индивидуальны и наполнены огромной энергией, инструментальное мастерство покоряло любую аудиторию, но выработанные им концепции не всегда были понятны даже его партнерам по ансамблю. Любопытно, что Коулман не сблизился с другими представителями фри-джаза ни в Америке, ни в Европе. Много времени уделял сочинению музыки для камерных ансамблей (три произведения были исполнены в 1985 году на фестивале в Хартфорде). Самая популярная тема Коулмана — Lonely Woman, менее известны Broken Shadows, Space jungle, Comme Il Faut, Love And Sex, Focus On Sanity.