Born in Skive, Würtz played his youth years at hometown club Skive IK. He made his senior debut for the club in the secondary Danish 1st Division league. In November 2001, he signed a three-and-a-half year contract with Aalborg Boldspilklub (AaB) in the top-flight Danish Superliga championship. Würtz was subsequently loaned out to Skive for six months, where he finished the 2001–02 season. He joined AaB in July 2002, and instantly became a mainstay in the first team starting line-up. In his debut season in the Danish Superliga 2002-03 season, he missed only one match, as he played 32 of 33 league games. In his first three seasons at AaB, Würtz only missed four of 99 Superliga games.