Cornetista, trompetista i compositor de jazz, fill del bateria Roy Haynes.

Va començar treballant amb grups electrònics, fins que va trobar, el 1979, el saxofonista Steve Coleman . Junts, van formar  Five Elements, que va ser una de les primeres influències del col·lectiu M-Base. Després de formar el seu propi grup, Graham Haynes and No Image, i publicar un àlbum, What Time It Be? Haynes es va dedicar a estudiar la música africana, aràbiga surasiàtica. Després de traslladar la seva residència a França, el 1990, Haynes va incorporar totes aquestes influències als seus nous discos, Nocturne Parisian i Griot’s Footsteps.

Haynes va tornar a Nova York el 1993, per posicionar-se en la florent escena Hip hop, recollint aquesta nova experiència en el seu àlbum Transition. Després d’editar un altre disc híbrid el 1996, Tones For The 21st Century, Haynes va descobrir el drum ‘n’ bass i va començar a treballar amb alguns dels millors DJs de Londres. El resultat va ser el seu disc publicat el 2000, BPM, una fusió de ritmes drum n’ bass amb música de Richard Wagner.

A través dels anys, Haynes ha elaborat nombrós material molt ben acollit per la crítica, tant en projectes multimèdia, com component la banda sonora del film Flag Wars and The Promise, o fent conferències a la New York University.

Ha col·laborat a més amb artistes com Roy Haynes (el seu pare), Cassandra Wilson, Vernon Reid , Meshell Ndegeocello, The Roots, David Murray, George Adams, Ed Blackwell, Bill Laswell, Steve Williamson, i Bill Dixon.