Würtz made his debut for the Denmark under-21 national team in August 2002. He played 17 under-21 national team matches until February 2005, taking over for Jan Kristiansen as team captain in September 2004. He debuted for the senior Danish national team on 2 June 2005, in a 1–0 friendly match win against Finland. He came on the pitch as a substitute for Danish team captain Jon Dahl Tomasson, and was supposed to hand over the captain's armband to Thomas Gravesen. When he approached Gravesen, he was told to take the armband himself and thus he captained the Danish national team for the final nine minutes of his debut game.