Gavin started to work professionally in 1979. In 1983–84 he toured as a member of Renaissance. He worked as a freelance session drummer on records and tours for the following artists: Incognito, Lisa Stansfield, Lewis Taylor, Artful Dodger, Paul Young, Iggy Pop, Level 42, Porcupine Tree, OSI, King Crimson, Shooter, Dizrhythmia,The Kings Of Oblivion, Sam Brown, Tom Robinson, Go West, Black, Gail Ann Dorsey, B J Cole, Dave Stewart, Barbara Gaskin, Nathan East, Yasuaki Shimizu, Camouflage, Kevin Ayers, Claudio Baglioni, Franco Battiato, Chizuko Yoshihiro, Jakko, Richard Barbieri, Mick Karn, Eros Ramazzotti, Devogue.
In 2008, Gavin joined King Crimson as part of a dual-drummer line-up with Pat Mastelotto. Gavin played a number of shows in the United States in August with the band.
On 23 August 2011 he was a featured performer on the 'Late Show with David Letterman' as part of their second "Drum Solo Week", along with such players as Stewart Copeland, Neil Peart, and Dennis Chambers.
In September 2014, Harrison plays live in the new seven-member formation of King Crimson, as one of the three drummers.
He won the Modern Drummer magazine readers' poll for "best progressive drummer of the year" consecutively from 2007–2010. He won "Best Prog Drummer" in DRUM USA magazine 2011. He is the featured cover story on Modern Drummer January 2009. Rolling Stone Magazine polls rate him as the third best drummer in the past 25 years. Best Prog Drummer 2011 & 2012 in Prog Magazine. In 2014, Modern Drummer magazine placed Gavin in the Top 50 Greatest Drummers of all Time.
Harrison has authored two instructional drum books entitled Rhythmic Illusions and Rhythmic Perspectives. He also wrote and produced his own instructional DVDs, Rhythmic Visions and Rhythmic Horizons, at his home studio. 2010 saw the release of Rhythmic Designs, a book of transcriptions by Terry Branam, and a 3-hour DVD of Gavin's explanations and demonstrations. It won 'Best in Show' at the summer NAMM show in the USA. 2014 sees the release of "Rhythmic Compositions" a book of 20 detailed drum transcriptions (by Terry Branam) of recorded Porcupine Tree performances – plus photos and stories of the recording and creative process.