National military and veteran service organizations (MVSOs) have the potential to be advocates for stronger military tobacco control. This study consisted of qualitative analysis of interviews with 5 MVSO leaders (or their designees) and 6 focus groups conducted with veterans, to explore the opinions of MVSO leaders and veterans about military tobacco use and tobacco control policy, and to assess their current knowledge, attitudes, and likelihood of engaging with civilian tobacco control. Themes discussed include the impact of tobacco use on the military mission and on veterans; the possibility of stronger military tobacco control policies; and the idea that such policies would affect the rights of military personnel. Participants considered whether tobacco use impacts the military mission in the most literal sense (e.g., giving away patrol locations), ignoring larger scale effects on long term health and costs. While familiar with tobacco's impacts on veterans' health, MVSO leaders did not endorse stronger policies, although some veterans did. Participants were largely unaware of the impact of tobacco use on military readiness. Establishment of better alliances among MVSOs and civilian public health groups for mutual education about tobacco's many negative effects on the military's mission may be necessary to achieve a tobacco-free military.