W latach 2000–2004 występował w lidze uniwersyteckiej NCAA w zespole „Saint Joseph’s Hawks” Saint Joseph’s University w Filadelfii. Po roku występów został uznany za najlepszego debiutanta NCAA przez „Sports Illustrated” i serwis internetowy CBS Sportsline. W sezonie 2003/04 poprowadził swój zespół do zwycięstwa w rundzie zasadniczej NCAA (27 wygranych, bez porażki) i awansu do najlepszej ósemki ligi. Zespół Saint Joseph’s University, dla którego był to najlepszy sezon w historii, był jeszcze o krok od awansu do czołowej czwórki, ale o jego porażce przesądził rzut za trzy punkty na kilka sekund przed końcem meczu z ekipą z Oklahomy.
Statystyki Nelsona w sezonie 2003/04 – 20,6 zdobytych punktów, 5,3 asyst, 2,9 przechwytów na mecz – przyniosły mu uznanie zarówno na macierzystej uczelni (stał się rekordzistą w historii drużyny w tych trzech elementach, a jego numer na koszulce – 14 – zastrzeżono), jak i wśród specjalistów koszykówki. Otrzymał m.in. kilka prestiżowych nagród w 2004 – John R. Wooden Award i tytuł Naismith College Player of the Year.
W drafcie NBA w 2004 r. został wybrany z numerem 20. przez Denver Nuggets[1], lecz wkrótce został wymieniony do Orlando Magic za wybór w pierwszej rundzie przyszłego draftu[2]. W drużynie Magic debiutował w sezonie 2004/05, występując głównie jako zmiennik rozgrywającego Steve’a Francisa. Pod koniec sezonu, kiedy Francis został przesunięty na pozycję rzucającego obrońcy, Nelson zajął jego dotychczasowe miejsce głównego rozgrywającego. Został wybrany do drugiej piątki najlepszych debiutantów NBA. Jego pozycja w Orlando Magic umocniła się, kiedy w lutym 2006 Francis przeszedł do New York Knicks. W sezonie 2008/09 został on nominowany jako rezerwowy do All-Star Game oraz konkursu Skills Challenge podczas Weekendu Gwiazd[3]. Nie mógł tam jednak wystąpić z powodu kontuzji barku[4]. Do gry po kontuzji powrócił dopiero na pierwszy mecz finałów 2009[5], w których Magic przegrali z Los Angeles Lakers 4–1[6].
30 czerwca 2014 został zwolniony przez Magic[7]. 24 lipca 2014 podpisał kontrakt z Dallas Mavericks[8].