Background Physical inactivity is associated with several diseases, but studies evaluating the association between chronic musculoskeletal complaints (MSCs) and physical exercise have shown conflicting results. The aim of this large-scale prospective population-based study was to investigate the association between self-reported physical exercise at baseline and the prevalence of chronic musculoskeletal complaints (MSCs) 11 years later. Methods The results are based upon two consecutive public health studies conducted within the county of Nord-Trøndelag, Norway (The HUNT studies). A total of 39,520 (83%) out of 47,556 adults who participated in HUNT 1 and HUNT 2 responded to questions about physical exercise at baseline in 1984–86, and to questions about musculoskeletal complaints 11 years later (1995–97). Chronic MSCs was defined as MSCs ≥ 3 months during the past year, and chronic widespread MSCs such as pain ≥ 15 days during the last month from the axial region, above the waist, and below the waist. Associations were assessed using multiple logistic regression, estimating prevalence odds ratio (OR) with 95% confidence intervals (CIs). All the final analyses were adjusted for age, gender, body mass index, smoking and education level. Results At follow-up 20,223 (51%) reported chronic MSCs, and among these 2,318 (5.9%) reported chronic widespread MSCs. Individuals who exercised at baseline were less likely to report chronic MSCs 11 years later (OR 0.91, 95% CI 0.85–0.97) than inactive persons. Among individuals who exercised more than three times per week, chronic widespread MSCs were 28% less common (OR 0.72, 95% CI 0.59–0.88) compared to inactive individuals. Conclusion In this large-scale population-based study, physical exercise was associated with lower prevalence of chronic MSCs, in particular chronic widespread MSCs. Future studies should try to clarify whether chronic MSCs are a cause or a consequence of inactivity.