Gordon worked with Lionel Hampton in 1961 and 1962 and with Lloyd Price and Sam Rivers later in the 1960s.
He also led his own ensembles in the late 1970s, with sidemen including Tolliver, Roland Alexander, Lisle Atkinson, Stanley Cowell, and Andrew Cyrille.
When Joiner left the group in the early 1990s, Gordon became its leader and changed its name to Trombones Unlimited.
In the 1990s he also played with Slide Hampton, Josh Roseman, Lafayette Harris, Martin Winder, Curtis Fuller, and Thilo Berg.
Gordon worked for several decades as a session musician for recordings and has also performed in pit orchestras for Broadway musicals.