Abstract Studies on measured physical fitness and oral health are sparse. The aim of this study was to investigate the associations between self-reported physical activity and measured physical fitness and oral health of young men. The study population consisted of 13,564 Finnish male conscripts who had mandatory clinical oral examinations and physical fitness tests at the beginning of military service in 2011. Finally, around 10,800 conscripts had physical fitness test outcomes available and a total of 8552 conscripts answered a computer-based questionnaire on background factors. Decayed Tooth (DT) and Decayed, Missing, or Filled Tooth (DMFT) indices, outcomes of surveys and fitness tests were used in analyses by cross-tabulation and multivariable logistic regression model (odds ratios [OR] with 95% confidence interval [CI]) were calculated. Regularly exercising conscripts had a reduced need for dental restorative treatment than those reporting no physical activity (p < 0.0001). The proportion of participants with sound dentition (DT = 0) increased steadily with increasing physical activity (39.0–59.4%). Good measured physical fitness was a protective factor against increased dental restorative treatment need. A low prevalence of smoking and low use of alcohol and energy drinks were associated with frequent exercise, whereas consumption of sport drinks and snuff use were common among those who exercised frequently. Good measured physical fitness and self-reported physical activity are associated with reduced caries burden. There is a need for information about the harms of tobacco products and the benefits of a healthy diet, even for the increased energy needs of the physically active.