Henderson played two years of college soccer at UCLA, where he helped the team win a national championship his sophomore season. Upon graduating from college, Henderson played for German Second Division club FSV Frankfurt during the 1994–95 season. After the end of that season, he moved to the Norwegian league, where he trained with Stabæk during the winter.
At the end of the Norwegian season, Henderson returned to the U.S. and on March 11, 1996, the Colorado Rapids of Major League Soccer (MLS) named Henderson as a Discovery Player. He immediately stood out by starting 29 games, scoring three goals and eight assists, and being named the Rapid's team MVP. Henderson spent the next two seasons with the Rapids, registering nine goals and 22 assists over 51 games. He then moved to the Kansas City Wizards for the 1999 season, where he started 29 games, scoring three goals and six assists. Henderson was even better in 2000, scoring nine goals and nine assists as one of the major players in the Wizards team that won the MLS Cup.
He moved to the Miami Fusion for the 2001 season where he scored three goals and eight assists on a team that went on to win the MLS Supporters' Shield in their final year. Upon the Fusion's contraction, Henderson was reacquired by the Rapids in the 2002 MLS Dispersal Draft. Henderson continued to be a threat on the right for the Rapids, scoring 11 goals and seven assists in his first season back. Although he began to show his age in the next two seasons, Henderson continued to be dangerous on the flank. He is the Rapids' all-time leader with 178 games played, 53 assists, and 120 points. Henderson was traded to the Columbus Crew in May 2005 in a three-team deal. After the season, he was dealt again, to the MetroStars — soon renamed New York Red Bulls — for Tim Ward. Henderson played every match of the 2006 season, and by its end he was the league's all-time leader in games played, though he has since lost the title. At the end of the season, however, Henderson was waived. He went on to announce his retirement from professional soccer on December 22, 2006.
Following his retirement as a player, Henderson rejoined the Kansas City Wizards as an assistant coach for the 2007 season. On January 24, 2008, it was announced that Henderson would be joining the front office of the Seattle Sounders FC as the technical director.
Henderson earned 79 caps with the U.S. national team throughout the 1990s. He first appeared for the U.S. while still at UCLA when he started in a victory over Iceland. He quickly established himself on the national team, seeing time in nearly every game leading up to the 1990 FIFA World Cup. While he was on the U.S. roster at the World Cup – and the tournament's youngest player at 19 – he did not enter any of the three U.S. games. Henderson was a member of the U.S. team at the 1992 Summer Olympics in Barcelona.
Henderson continued to play with the national until 1998. His last game in the 1990s came in a February 25, 1998 loss to Belgium as the U.S. prepared for the 1998 FIFA World Cup. Despite being a critical part of the national team for years, Henderson did not make the World Cup roster. Henderson did not earn his next cap until October 25, 2000. His next, and final cap, came on September 1, 2001. Over his national team career, Henderson accrued 79 caps but only three goals for the team. Despite all those caps, Henderson never played in a World Cup for the United States.