Harrison studierte in der High School in New Orleans unter Ellis Marsalis (der ihn in Bebop und Post-Bop Stilen unterrichtete), er zählt aber auch Drummer wie Roy Haynes (mit dem er 1979 arbeitete) und Art Blakey sowie Jack McDuff zu seinen Lehrmeistern sowie den klassischen New-Orleans Jazz. Sein Vater Donald Harrison Sr. war eine prominente Figur in der lokalen Tradition der „Mardi Gras-Indians“, die im Karneval die afrikanische Tradition von „call and response“-Gesängen (chants) pflegen (Harrison jr. selbst ist Big Chief der „Congo Nation“, in dem er auch seine eigenen Kostüme entwirft). In den 1980er Jahren spielte er (ab 1981) in Art Blakeys Jazz Messengern, in der Bigband von Dino Betti van der Noot und in einer Band mit Terence Blanchard bis 1989, der ebenfalls aus New Orleans stammt. In den 1990er Jahren spielte er mit den neu zusammengestellten The Headhunters, der Tour-Band von Herbie Hancock. Zu hören war er auch auf Dr. Lonnie Smiths Album Rise Up! (2009).
Harrison kann in fast allen Jazz-Stilen spielen. Er selbst sieht sich als Begründer und Protagonist eines „Nouveau Swing Styles“, der Swing-Rhythmen mit Rhythm and Blues, Hip-Hop, Mardi-Gras-Indian-Music und Reggae mischt. Hinzu kommen Ausflüge in Rap und Funk.
Terence Blanchard & Donald Harrison Eric Dolphy and Booker Little remembered at Sweet Basil 1, 2, Evidence 1986 (mit Mal Waldron, Richard Davis, Ed Blackwell)
