Garrett wurde mit Jazzmusik groß – sein Vater spielte Tenorsaxophon – und erlernte schon als Kind das Saxophonspiel; sein Instrument ist das Altsaxophon. Während eines Gastspiels wurde er vom Duke Ellington Orchestra als Ersatz-Saxophonist engagiert, er war dann dreieinhalb Jahre Mitglied des Orchesters. 1982 ging er nach New York City. Dort spielte er in Bands unter Freddie Hubbard und Woody Shaw und mit Art BlakeysJazz Messengers. International bekannt wurde er durch die 1989 und 1990 erschienenen Alben Amandla und Dingo, die er mit dem Trompeter Miles Davis eingespielt hatte. In der Folge erschien eine Reihe eigener Alben. Er arbeitete zusammen mit den Gitarristen Pat Metheny und John Scofield, mit den Pianisten Mulgrew Miller und Cornelius Claudio Kreusch sowie mit dem Bassisten Charnett Moffett, mit Rockmusikern wie Sting, Peter Gabriel und Bruce Springsteen und dem RapperGuru.
Im Bereich des Jazz war er laut Tom Lord zwischen 1981 und 2016 an 202 Aufnahmesessions beteiligt.[1]
1997, 2007 und 2012 wurde er für den Grammy nominiert. 1996 bis 1999, 2009, 2010, 2012, 2013 und 2014 gewann er den Leser-Poll von Down Beat in der Sparte Altsaxophon und 1997 den Leser-Poll für Pursuance als Jazz-Album des Jahres.