Smokeless tobacco use is a significant health risk for carcinoma of the oropharynx, and has a high prevalence in the southern United States. To evaluate the potential demand for a smokeless tobacco cessation program, we surveyed patients attending the General Medicine Clinic of a Veterans Affairs Medical Center. The prevalence of smokeless tobacco use was 5.8%, which did not justify creation of a clinic-based cessation program. Since we observed adults using smokeless tobacco as a means to reduce or stop their smoking, smoking cessation programs should include counseling against smokeless tobacco use.