The association of body mass index (BMI; kg/m2) with overall and site-specific cancer mortality in Asians is not well understood. A total of 113,478 men from the Korean Veterans Health Study who returned a postal survey in 2004 were followed up until 2010. The adjusted hazard ratios (HRs) of cancer mortality were calculated using a Cox model. During 6.4 years of follow-up, 3478 men died from cancer. A reverse J-curve association with a nadir at 25.0 to 27.4 kg/m2 was observed. Below 25 kg/m2, the HRs of death for each 5 kg/m2 decrease in BMI were 1.72 (95% confidence interval = 1.57–1.90) for overall cancer; 3.63 (2.57–5.12) for upper aerodigestive tract (UADT) cancers, including oral cavity and larynx [HR = 4.21 (2.18–8.12)] and esophagus [HR = 2.96 (1.82–4.81)] cancers; 1.52 (1.35–1.71) for non-UADT and non-lung cancers, including stomach [HR = 2.72 (2.13–3.48)] and large intestine [HR = 1.68 (1.20–2.36)] cancers; and 1.93 (1.59–2.34) for lung cancer. In the range of 25 to 47 kg/m2, the HRs for each 5 kg/m2 increase in BMI were 1.27 (1.03–1.56) for overall cancer mortality and 1.57 (1.02–2.43) for lung cancer mortality. In individuals <25 kg/m2, inverse associations with mortality from overall cancer and non-UADT and non-lung cancer were stronger in never-smokers than in current smokers. Both low and high BMI were strong predictors of mortality from overall and several site-specific cancers in Korean men. Further research is needed to evaluate whether interventions involving weight change (loss or gain) reduce the risk of cancer or improve the survival.