Introduction: Rates of tobacco use in the U.S. military have traditionally been higher than in the general U.S. population. While the military has experienced decreases in tobacco use over the past two decades, recent surveys suggest a trend of increased use. Given the negative impact of tobacco on both the readiness and the long-term health of military members, it is important to understand what factors may be related to the increased use rates. It has been suggested that there is a culture that supports tobacco use in the military. Methods: We examined perceptions about the climate of tobaccocontrol among military installation Tobacco Control Managers and Service Policy Leaders from all four branches of the military (n = 52) using semistructured interviews. Results: The primary strength of the military's tobacco control program, according to the participants, was mandating the provision of treatment services on every military installation. Any military member can receive both counseling and pharmacotherapy for tobacco. Opinions vary on the most promising new strategies for tobacco control. Many have pushed for a completely tobacco-free Department of Defense, including requiring troops to be tobacco-free and banning tobacco sales on military installations. However, a number of tobacco control experts within the military worry about unintended consequences of a complete ban. Discussion: While several benefits of the current tobacco control program were identified, opportunities for improvement were identified at both the installation and service level.