Background: The negative impact of maternal smoking during pregnancy on offspring semen quality is well established. Less is known about the impact of paternal smoking. Methods: We estimated differences in semen parameters and testicle size according to paternal smoking in 772 adult sons of women enrolled in the Danish National Birth Cohort when pregnant. Parents’ smoking was reported around gestational week 16, and analyses were adjusted for parents’ ages at conception, maternal pre-pregnancy body mass index, maternal alcohol and caffeine intake, family occupational status, ejaculatory abstinence time, clinic of semen analysis, and season. Results: Sons of smoking fathers and non-smoking mothers had a 10% (95% confidence interval: −24%, 7%) lower semen concentration and 11% (95% confidence interval: −27%, 8%) lower sperm count than sons of non-smoking parents. Having two smoking parents was associated with 19% reduction in sperm count (95% confidence interval: −37%, 3%). Paternal smoking was not associated with volume, motility, or morphology. Adjusting for maternal smoking, paternal smoking was associated with a 26% increased risk of small testicular volume (95% confidence interval: 0.89, 1.78). Discussion: Exclusion of sons with a history of testicular cancer, chemotherapy, orchiectomy, and with only one or no testicles may have caused us to underestimate associations if these men's reproductive health including semen quality are in fact more sensitive to paternal smoking. Conclusion: The study provides limited support for slightly lower sperm concentration and total sperm concentration in sons of smoking fathers, but findings are also compatible with no association.