In 1994, the Minnesota Twins drafted Walker with the 8th pick in the 1st Round of the amateur draft. On August 30, 1996, Walker made his major league debut with the Twins. In 1998, Walker became the starting second baseman for the Twins, hitting .316 with 12 HR, 62 RBIs, and a career best 19 stolen bases.
Over the next season and a half, Walker's offensive performance began to decline, and the Twins traded Walker to the Colorado Rockies. He responded by hitting .316 through the rest of 2000 and .297 through the first half of 2001. Walker hit 12 home runs as a member of the Rockies that year.
The Cincinnati Reds, in need of a better performance from its second base position, traded for Walker in July 2001. Walker rewarded the Reds by providing consistent offense, hitting .295 through the end of the season. In 2002, Walker enjoyed another fine year, hitting .299 with 11 HR and 64 RBIs and setting career highs with 42 doubles and 155 games played.
Following the season, the Boston Red Sox hired Theo Epstein as their new General Manager. One of his first moves was trading for Walker. During 2003, Walker continued to provide consistent offense, hitting .283 with 13 HR and setting a career high with 85 RBIs. On September 23 that year, with the Red Sox trailing the Baltimore Orioles 5-2 in the ninth inning, Walker hit a two-out, two-strike, three-run home run off Jorge Julio to tie the game. (The Sox won, 6-5, on David Ortiz's walk-off home run in the tenth.) The Red Sox made the playoffs and Walker stepped up his performance again; he hit .313 with three homers in the American League Division Series against the Oakland A's, and .370 with two more homers and hits in every game against the New York Yankees in the ALCS. The Red Sox were eliminated in 7 games. Walker's 5 postseason homers are still a Red Sox record. Despite his performance, Walker was allowed to leave, signing with the Chicago Cubs via free agency.
Over the next three seasons, Walker attempted to maintain his offensive performance with the Cubs, but found himself playing less, platooning with younger players. Walker hit .274 (2004), .305 (2005), and .277 (through July 2006). However, he began to share time at second base with other players like Neifi Pérez, and started to make appearances at first base and in the outfield.
At the end of July 2006, the San Diego Padres were attempting to make the playoffs while the Cubs were already out of the race. Before the trading deadline, the Padres traded low-A pitching prospect José Ceda to the Cubs for Walker, who became the new starting third baseman. He hit .282 down the stretch, and the Padres made the playoffs, but were eliminated in the first round by the St. Louis Cardinals.
In 2007, Walker attended spring training with the Padres. However, during the offseason, the Padres had restocked the team with more infielders and left-handed hitters, and after a poor performance during the exhibition season, Walker was released on March 27. On March 30, 2007, he signed with the Oakland A's.