Only a few studies have been published of the outcome of adolescent headache (HA). The aim of this study was to examine the predictors of the outcome of headache frequency. A population-based sample of 13-year-olds with or without HA (N = 228) was followed to the age of 16 years. HA was classified on the basis of a face-to-face interview and clinical examination. The outcomes of monthly HA (>1/month) and non-frequent HA (0–1/month) were studied. Frequent use of analgesics, female gender and multiple non-headache pain predicted the persistence of monthly HA (>1/month). Significant predictors for worsening non-frequent HA (from 0 to 1/month to >1/month) were female gender, consistent migraine and high basic educational level of one parent. Adolescents frequently using analgesics constitute a risk group for a poor outcome of HA. Especially girls meeting this criterion should be considered a target group in the planning and implementing of preventive measures.