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 Aarhus GF.
Interlandcarrière
Nielsen speelde in totaal 54 officiële interlands (drie goals) 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.