Distress tolerance (DT), defined separately as the actual or perceived ability to withstand aversive affective states, has been linked to problematic substance use behavior within nonclinical samples and treatment outcome among those with substance use disorders. Thus, DT may represent an important risk factor for substance use relapse, and has been evaluated as a target of substance use treatment. However, the longitudinal trajectory of DT among treatment seeking substance users remains unknown. The aims of the current study were to (a) characterize trajectories of perceived DT, assessed via self-report, and behavioral DT, assessed using a behavioral task, and (b) evaluate the influence of abstinence duration and frequency of use as predictors of DT change in a sample of residential treatment seeking substance users. Results of latent curve model analyses revealed that both perceived and behavioral DT improved nonlinearly over time. Additionally, abstinence duration was associated with greater improvement in both perceived and behavioral DT, and greater frequency of use post-treatment was associated with attenuated behavioral, but not perceived, DT. The current study provides evidence for naturally occurring improvement in both perceived and behavioral DT over 12 months following completion of residential substance use treatment. Such findings provide support for the conceptualization of DT as a malleable treatment target and emphasize the importance of abstinence in DT improvement and substance use recovery.