Info:
Haynes ist Sohn des Jazzschlagzeugers Roy Haynes, durch den er schon früh in Kontakt mit großen Musikern kam. Mit seinem Schulfreund Marcus Miller sammelte er erste musikalische Erfahrungen in Schulbands, stieg dann aber vom Drumset auf die Trompete um, mit 16 Jahren auf das Kornett, das ihm ein lyrischeres Spiel abverlangte. Unterricht hatte er bei Dave Burns. Während seiner Zeit auf dem Queens College (1977 bis 1980) spielte er zunächst in Gospelgruppen. 1979 traf er das erste Mal den Altsaxophonisten Steve Coleman und spielte in seiner Gruppe. Gemeinsam mit Kim Clarke, Jean-Paul Bourelly, Cassandra Wilson und Schlagzeuger Mark Johnson gründeten die beiden Bläser die Band Five Elements, die zunächst hauptsächlich auf der Straße spielte, in den fortschreitenden 1980ern aber als M-Base Collective große Erfolge feierte.
1987 gründete er u. a. mit dem M-Base-Gitarristen David Gilmore die Band No Image, arbeitete aber auch häufig mit John Zorn und mit Elliott Sharp. Anfang 1991 war er an dem Album David Murray Big Band Conducted by Lawrence „Butch“ Morris beteiligt. Dann ging er für drei Jahre nach Paris, wo er einerseits mit afrikanischen und arabischen Musikern zusammenarbeitete, aber auch mit Ed Blackwell, Don Byron, Nicolas Simion, Steve Williamson und Rodney Kendrick spielte. Er veröffentlichte die beiden Alben Nocturne Parisian (1992) und The Griot's Footsteps (1994). Nach New York zurückgekehrt, beschäftigte er sich mit der blühenden Hip-Hop-Szene und ließ das Album Transition mit Rap-Elementen und 1996 Tones For The 21st Century folgen. Auf B.P.M. fusionierte er Drum-and-Bass-Beats mit der Musik eines Richard Wagner. Seitdem hat er sich mit Multimedia-Projekten beschäftigt, Filmmusiken geschrieben und an der New York University gelehrt.
Haynes arbeitete auch mit Bill Dixon (17 Musicians in Search of a Sound: Darfur), Me’shell Ndegeocello, Vernon Reid, The Roots, David Murray, George Adams, Uri Caine, Bheki Mseleku, Rod Williams und Bill Laswells Bandprojekt Arcana. 2018 gehört er dem Vijay Iyer Sextet an (Wikipedia).