Nielsen begon zijn loopbaan bij Brønshøj BK, speelde twee seizoenen voor Brøndby IF en vertrok in 1989 naar Aston Villa. Hij speelde drie seizoenen voor de club uit Engeland, waarna hij terugkeerde naar zijn vaderland en zich aansloot bij AGF Århus. In juli 1994 beëindigde Nielsen zijn voetballoopbaan.
Nielsen speelde in totaal vierenvijftig officiële interlands (drie doelpunten) voor Denemarken. Onder leiding van bondscoach Sepp Piontek maakte hij zijn debuut op 5 oktober1983 in de OS-kwalificatiewedstrijd tegen Polen (1-1) in Aarhus, net als Lars Lunde (Brøndby IF) en Kim Vilfort (BK Frem). Hij nam met zijn vaderland deel aan het door de Denen gewonnen EK voetbal 1992.