Introduction: As South Korea remains technically at war with the North, higher smoking prevalence in the military might adversely affect the South Korea's military power and contribute to lifetime smoking in men with mandatory military service. This study was to identify priorities among the anti-smoking strategies to improve the existing smoking cessation programs for the Korean military. Methods: The analytic hierarchy process model with a goal, decision criteria, and sub-criteria as well as candidate strategies, was developed following a literature search and expert group discussion. A survey for pairwise comparison was conducted to determine the priority of the (sub-)criteria and strategies by 14 experts. The Super-Decisions software was used to determine the priorities and to analyze their consistency ratios and sensitivities. The study was approved by the ethics committee of the Korea Ministry of Health and Welfare. Results: Eight candidate strategies were developed to improve the effectiveness of military anti-smoking interventions as follows: (1) development of outcome enhancement plans for smoking cessation programs for the military, (2) development of differentiated smoking cessation programs for specific groups, (3) building of community network for continuity and accessibility of anti-smoking project, (4) building of industry-academia-government networks for anti-smoking project, (5) improvement of the perception of and strengthen the reward for smoking cessation, (6) development of a training system for army clinicians for the delivery of smoking cessation services, (7) creation of a certification system for smoking cessation programs, and (8) development of an evaluation system of project performance for smoking cessation. Through the analytic hierarchy process survey, the military specificity and its sub-criterion of practicality were selected as the top concerns of decision criteria for the anti-smoking strategies among the decision criteria of outcome improvement, military specificity, publicness, and economic efficiency. The most important strategy was to improve the perception of and strengthen the reward for smoking cessation. This strategy was most focused on the creation of an anti-smoking environment and improvement of the effectiveness of the projects. The creation of a training system for army clinicians for the delivery of smoking cessation services ranked second. Conclusion: In conclusion, motivating smoking cessation and utilizing well-trained army clinicians were found to be the most important anti-smoking strategies for the Korean military. This study might provide valuable insights for policy makers to reduce tobacco use in the Korean military.