Comenzó trabajando con grupos electrónicos, hasta que encontró, en 1979, al saxofonista Steve Coleman. Juntos, formaron una banda denominada Five Elements, que fue una de las primeras influencias del colectivo M-Base. Tras formar su propio grupo, "Graham Haynes and No Image", y publicar un álbum, What Time It Be?, Haynes se dedicó a estudiar la música africana, arábiga surasiática. Tras trasladar su residencia a Francia, en 1990, Haynes incorporó todas esas influencias a sus nuevos discos, Nocturne Parisian y Griot's Footsteps.
Haynes regresó a Nueva York en 1993, para posicionarse en la floreciente escena Hip hop, recogiendo esta nueva experiencia en su álbum Transition. Tras editar otro disco híbrido en 1996, Tones For The 21st Century, Haynes descubrió el drum 'n' bass y comenzó a trabajar con algunos de los mejores DJs de Londres. El resultado fue su disco publicado en 2000, BPM, una fusión de ritmos "drum n' bass" con música de Richard Wagner.
A través de los años, Haynes ha elaborado numeroso material muy bien acogido por la crítica, tanto en proyectos multimedia, como componiendo la banda sonora del film "Flag Wars and The Promise", o dando conferencias en la New York University. Ha colaborado además con artistas como Roy Haynes (su padre), Cassandra Wilson, Vernon Reid, Meshell Ndegeocello, The Roots, David Murray, George Adams, Ed Blackwell, Bill Laswell, Steve Williamson, y Bill Dixon.
