Nelson attended Chico High School in Chico, California, before transferring to St. Joseph Notre Dame in Alameda, California. At St. Joseph, Nelson played basketball on the 1992 California State Division I Championship team with NBA star Jason Kidd.
After being selected twice by the Toronto Blue Jays in the 1993 and 1994 amateur drafts, he was drafted by the Atlanta Braves in the fourth round of the 1996. Nelson made it to the majors in 2001, seeing two stints of an inning apiece in mop-up duty, where his ERA was 36.00.
Nelson re-signed with the Red Sox in the spring of 2004, and was promoted to the majors in June as bullpen help. After recording a scoreless inning against Texas, he gave up 5 runs over 12⁄3 innings in his next two appearances. He was optioned back to Triple-A when Mark Malaska was activated off the disabled list.
After spending spring training with the New York Mets in 2005, he signed to play with the Devil Rays' Triple-A team. Despite good peripheral numbers of 61 strikeouts in 46 innings and a .229 opponents' batting average, he went 0-3 with a 4.11 ERA and was released in July. Nelson then had a short 13-inning stint with the Cardinals' Double-A club, allowing just four hits over that span. He signed with the Kansas City Royals organization in November.
Nelson bounced between Omaha and the major-league club before being called up for good on July 19, 2006. After Royals closer Ambiorix Burgos was demoted on August 14, Nelson threw a perfect ninth inning the following day. Manager Buddy Bell used the 31-year-old journeyman in the closer's role for 2006. In 2007, he was hurt. At the end of the 2007 season, he was designated for assignment to Triple-A Omaha, which he refused and opted out becoming a free agent. In December 2007, Nelson was signed by the Florida Marlins to a minor league contract.
Joe Nelson earned a victory over the Mets in his final appearance with the Marlins on September 28, 2008, becoming the last recorded winning pitcher at Shea Stadium.