Iodization of salt is an effective strategy to prevent iodine deficiency disorders. Recent studies, however, indicate that increasing the iodine intake in a population may give rise to an increased incidence of hypothyroidism, but the association has not been fully clarified. In Denmark, iodization of salt was initiated in 1998 because of mild-to-moderate iodine deficiency. The aim of this study was to evaluate the effect of the raised iodine intake on the nationwide incident use of thyroid hormone replacement therapy (levothyroxine) to treat hypothyroidism. Data on all use of levothyroxine was extracted from the Register of Medicinal Product Statistics during the period 1995–2009 and linked to other nationwide registers by use of the Danish identification number. Persons with previous thyroid surgery were excluded. In the studied period 71,565 incident users were identified. The incidence rate increased 75% in the moderately iodine deficient region (72.2 incident users/100,000 person-years in 1997 to 126.6 in 2008) and 87% in the mildly deficient region (86.9–162.9). When stratified by sex and age-group (00–39, 40–64, 65+) the largest relative increase was seen among women in the youngest age-group, where more than a doubling was seen. The mechanisms behind the increase may be a result of iodine-induced hypothyroidism, although a higher diagnostic activity with regard to thyroid dysfunction and intensified treatment of subclinical hypothyroidism may also play a role. Our findings stress the need for caution when initiating iodine fortification programs to keep the intake within the optimal range, and the need for continuous monitoring.