Dallas Mavericks (2003-2004)

Devět a půl dne před začátkem sezóny 2003-2004 byl Walker vyměněn do Dallasu. Ovšem v Texasu nedostával tolik příležitostí jako by si představoval, jelikož Mavericks získali Antawna Jamisona. Walker zakončil základní část s průměry 14 bodu, 8,3 doskoku a 4,5 asistence. Dallas postoupil do playoff, ale hned v prvním kole vypadl se Sacramentem Kings 4-1 na zápasy.

Atlanta Hawks (2004-2005)

V Dallasu strávil jeden rok a byl vyměněn do Atlanty. Dne 8.8.2004 se Walker a Tony Delk stěhovali do Atlanty - opačným směrem putovali Jason Terry, Alan Henderson a draftový výběr. Za Atlantu odehrál 53 zápasů a vracel se zpět do Bostonu.

Boston Celtics (2005)

24. února 2005 poslal Boston do Atlanty Garyho Paytona (ten byl ovšem následně propuštěn, aby znovu podepsal smlouvu se Celtics), Toma Gugliottu, Michaela Stewarda a výběr v prvním kole draftu. Walker odehrál ve známém dresu všech zbývajících 24 zápasů s průměry 16,3 bodu, 8,3 doskoku a 1,1 bloku. Celtics postoupili do playoff, kde je ale ihned vyřadila Indiana v sedmi utkáních.

Miami Heat (2005-2007)

V létě (2. srpna 2005) byl vyměněn spolu s Paytonem do Miami, ve výměně pěti týmů a celkem třináctkou hráčů (byl to zatím největší trade v historii NBA)! Walker byl spíše vnímán jako rezerva, ale i přesto dokázal zakončit sezónu s průměry 12,2 bodu a 5,1 doskoku za průměrné 26,8 minuty. Avšak v playoff se jeho minutáž zvýšila a on vedl Heat v zápasech proti Nets a Pistons.

Heat dokázali postoupit až do finále NBA, když cestou porazili Bulls 4-2, Nets 4-1, ve finále konference udolali silné Pistons 4-2 a ve finále NBA si poradili s Dallasem 4-2 na zápasy, což byl pro floridský tým první titul v klubové historii. Walker slavil svůj první a zároveň poslední titul v kariéře. Celé playoff si připisoval velmi solidní průměr (13,3 bodu, 5,6 doskoku za 37,5 minuty) a nastoupil ve všech 23 zápasech v základní sestavě.

Následující ročník 2006-2007 klesl jeho pobyt na palubovce na 23,3 minut. Walker si připisoval "jenom" 8,5 bodu, 4,3 doskoku a 1,7 asistence. Heat se chtěli znovu pokusit dojít až do finále NBA, ale hned v prvním kole jim stopku vystavili Bulls, kteří je porazili hladce 4-0. Walker si připisoval 11,8 bodu a 2,3 doskoku a bylo to jeho poslední playoff v kariéře.

Minnesota Timberwolves (2007-2008)

24. října 2007 byl vyměněn do Minnesoty společně s Michaelem Doleacem, Waynem Simienem. Boston poslal Vlkům ještě výběr v prvním kole draftu a peněžní vyrovnání - to vše za Rickyho Davise a Marka Blounta. Walker odehrál za Timberwolves 46 zápasů s průměry 8 bodů, 3,7 doskoku. Minnesota se do playoff neprobojovala.

28. června 2008 byl vyměněn do Memphisu společně s Marko Jaričem, Gregem Bucknerem a s právy na O.J. Maya za Mikea Millera, Briana Cardinala, Jasona Collinse a práva na Kevina Lovea. Walker odehrál za Memphis pouze dva předsezóní zápasy a dva měsíce seděl pouze na lavičce náhradníků. Příležitost vůbec nedostal a 19. prosince 2008 byl propuštěn.

Tímto pro něho anabáze v NBA skončila.