Nielsen, bijgenaamd "Tist", speelde in totaal 38 interlands (52 goals) voor de Deense nationale ploeg, waarmee hij in 1912 deelnam aan de Olympische Spelen in Stockholm. Daar won de selectie de zilveren medaille, net als vier jaar eerder in Londen. In de finale, gespeeld op 4 juli1912 in het Olympisch Stadion, was Groot-Brittannië met 4-2 te sterk. Hij scoorde gemiddeld 1,37 goal per wedstrijd voor de Deense nationale ploeg. Zijn doelpuntentotaal werd op 24 juni2010 geëvenaard door Jon Dahl Tomasson in een WK-wedstrijd tegen Japan.