Nielsen kwam tien keer uit voor Denemarken. Onder leiding van bondscoach Morten Olsen maakte hij zijn debuut op 7 september2002 in de EK-kwalificatiewedstrijd tegen de Noorwegen (2-2) in Oslo. Hij viel in die wedstrijd in de 90ste minuut in voor aanvaller Jon Dahl Tomasson (AC Milan).