Smokeless tobacco (ST) use has been associated with numerous negative health consequences, yet the prevalence of ST has increased dramatically since the 1970s. Young males in the military are at an elevated risk for ST use relative to the general population. Sixty active-duty male participants were identified as ST users during their annual preventive health screening and randomly assigned to minimal-contact intervention or usual care. Intervention participants were proactively contacted by phone and recruited, using a motivational interviewing style, for a cessation program consisting of a treatment manual, video, and two supportive phone calls from a cessation counselor. Sixty-five per cent (20/31) agreed to participate in the minimal-contact intervention. Three- and 6-month follow-up contacts found that the cessation rates reported by intervention participants were double those reported by participants receiving usual care (41% vs. 17% at 3 months, 37% vs. 19% at 6 months). These pilot study data suggest that proactive recruitment using a motivational interviewing approach to offer a treatment provides a good opportunity to reduce the use of ST in military settings.