Az észak-karolinai születésű muzsikus New Yorkban nőtt fel zenész családban, tehetségét hamar felfedezték, 18 évesen már Duke Ellington zenekarában dobolt. Manhattan jazzklubjaiban később olyan legendás előadókkal játszott együtt, mint Dizzy Gillespie, Charlie Parker, Thelonius Monk, Coleman Hawkings, Bud Powell, Charles Mingus vagy Miles Davis, Kenny Clarkkal együtt az első ütősök között volt, aki bebopot játszott. Saját együttesébein is olyan kiváló zenészek fordultak meg, mint Richie Powell, Clifford Brown, Sonny Rollins, Eric Dolphy, Stanley Turrentine, George Colemann, Donald Byrd, vagy Kenny Dorham.
A hatvanas években az első muzsikusok egyike volt, aki részese lett az afro-amerikai lakosság érdekeit képviselő polgárjogi mozgalomnak, 1960-as We Insist - Freedom Now! című kompozíciója nagy sikert aratott, azonban az amerikai lemezipar évekig feketelistára tette. Kísérletező kedve mindvégig megmaradt, újszerű hangzásvilágokat és ritmusképleteket alkotott, háromnegyedes ütemet vezetett be a hard bop világába, dupla kvartettet, egy jazz kvartett és egy vonósnégyes kombinációját is vezetett, rap elődaókkal, DJ-kkel és avantgárd művészekkel is alkotott közösen. Kompozícióit nem csak saját együttesei számára írta, gospel kórusok és szimfonikus zenekarok, így a Bostoni Szimfonikusok is előadták műveit. Temetésén számos kiváló előadó, többek közt Randy Weston, Billy Taylor, Cassandra Wilson és Jimmy Heath is zenével vett végső búcsút.
