Distress intolerance is a key vulnerability factor implicated in the maintenance and relapse of cigarette smoking. Yet, past work has not examined changes in these processes during smoking cessation treatment or their relation to smoking cessation outcomes. The aim of the present study was to examine the effect of two smoking cessation interventions on changes in self-report and behavioral distress intolerance indices during treatment, and whether these changes are associated with smoking cessation outcomes. Treatment-seeking smokers (N = 384) were randomly assigned to one of two 4-session smoking cessation treatment programs: Standard Cessation Program (SCP) or Smoking Treatment and Anxiety Management Program (STAMP). Quit dates were scheduled to coincide with the final treatment session. Physical domains of distress intolerance were assessed at baseline and at each weekly session, via the Discomfort Intolerance Scale (DIS; higher scores indicate more intolerance for discomfort) and Breath Holding Duration Task (shorter durations indicate more intolerance for respiratory distress). The STAMP condition produced a greater rate of reduction in DIS scores than did the SCP condition. Changes in DIS scores during treatment mediated the effect of STAMP treatment on 7-day point prevalence abstinence at Month 3 post-quit attempt. There were no treatment conditions differences in changes in Breath-Holding duration. Data suggest self-reported distress intolerance is malleable in the context of stress sensitivity reduction treatment, but not standard smoking cessation treatment, and such reductions may result in promotion of smoking abstinence.