Tobacco use is the single most important preventable cause of death in military personnel. The purpose of this randomized clinical trial was to evaluate the effectiveness of two behavioral interventions when added to nicotine-replacement therapy on smoking cessation. The sample of 512 included 52% active duty military, 29% family, 11% retirees, and 8% Department of Defense civilians. There was a main effect of compliance at the end of the program (EOP); 69% of those who attended 75% of the classes were abstinent from tobacco; regression analysis found the more intensive program to be twice as effective at EOP and at 3 months, an outcome not continued at 6 months. The longer, more intensive Vanderbilt University Medical Center program was significantly more effective at helping the civilian portion of the population (85% versus 60% in the American Cancer Society program) but not the active duty participants.