Background: Early smallpox and Bacillus Calmette-Guérin (BCG) vaccinations have been associated with reduced risk of cutaneous malignant melanoma (CMM). We assessed the association between pre-school smallpox vaccination and early-school BCG vaccination and CMM in a young Danish population. Methods: We conducted a register-based case-cohort study of individuals growing up during the phase-out period of smallpox and BCG vaccination in Denmark (born 1965–1976) utilising the decrease in vaccination during this period. Information on childhood vaccinations and potential confounders from Copenhagen school health records were linked with nationwide registers on cancer (CMM diagnoses), migrations and deaths by personal identification numbers. Results: The individuals were followed from age 18 until 31/12/2014 (maximum age at end of follow-up, 49 years). 188 cases of CMM occurred in the background population of 46,239 individuals; 172 CMM cases (91%) had full information and were analysed. The adjusted hazard ratio (HR) for CMM by BCG and/or smallpox vaccination compared with neither vaccine was 1.29 (95% confidence interval (CI) 0.72–2.31). For smallpox vaccination only, HR = 1.23 (95% CI 0.53–2.86) for BCG vaccination only, HR = 1.13 (95% CI 0.61–2.09) and for both smallpox and BCG vaccination, HR = 1.75 (95% CI 0.87–3.48) compared with none of these. Vaccination below the age of one year gave similar results. Conclusions: We found no strong beneficial effect of smallpox and BCG vaccination against CMM among young adult Danes and with broad confidence intervals our data alone could be compatible with both modest preventive effects, no effects, and modest harmful effects. Our estimates do not contradict a potential modest beneficial effect of neonatal vaccination.