Nielsen was born in Esbjerg, Denmark. Having never played a senior match, he moved abroad in 1989 to play for German Bundesliga team Bayern Munich at the age of 18. In his three years at the club, he played only six minutes in a single game in May 1991, as he came on as a substitute in a 7–3 win against Hertha Berlin. Failing to break through at Bayern Munich, he left the club in the summer 1991. Nielsen initially signed a three-year contract with FC Sion in June 1991, but he never played a game for the club. He swiftly moved back to Denmark, to play with Odense BK in the Danish Superliga championship, where he debuted in September 1991.
At Odense, he was a part of the team that won the 1993 Danish Cup and he was then brought to league rivals FC Copenhagen in 1994. He played a single season for the club, where he was team captain, before he moved to main rivals Brøndby IF in 1995. In his year at Brøndby, the club won the 1995–96 Danish Superliga championship, and Nielsen was named Brøndby IF 1995 Player of the Year. He was called up for the Danish national team under national manager Richard Møller Nielsen. Nielsen made his debut against Armenia on 16 August 1995. He came on as a substitute and following 45 seconds on the pitch, he scored the second goal in Denmark's 2–0 win. He was called up to represent Denmark at the Euro '96 tournament hosted by England, where he scored one goal in his only match, the 3–0 win against Turkey.
He permanently moved away from Tottenham after Euro 2000, in July 2000, to play for English First Division team Watford. He was signed by Watford manager Graham Taylor for £2.5million, which at the time was the highest fee the club had ever paid for a player. After three seasons at the club, Nielsen returned to Denmark in 2003 for Superliga relegation battlers Herfølge Boldklub in a role as player/assistant coach. Following a bad first half of the 2003–04 season, head coach Johnny Petersen was fired and Nielsen was promoted to player/coach, in a coaching partnership with former national team player and Esbjerg native Michael Schjønberg. They managed to finish just above the relegation zone at the end of the season. For the subsequent 2004–05 season, Nielsen decided to focus exclusively on coaching, but to no avail as Herfølge was relegated, and he announced his coaching days were over.
Today he works as coach at Birkerød Sports College.