Objectives: We sought to determine the main factors related to relapse in patients with substance-related disorders (SRDs) who received methadone maintenance therapy (MMT) using decision tree (DT) analysis. Methods: We conducted a cross-sectional study of 4175 patients referred to the 45 MMT centers in Kermanshah province, west of Iran. We included all patients who were under MMT for at least one year. All information was collected through an interview by a psychologist. Descriptive statistics and univariate and multiple regression models were used in statistical analysis. The Gini index was calculated to determine the cut-off point of nodes. We used the Classification and Regression Trees algorithm to create the DT. Results: The relapse rate was 76.6% for all participants, with no significant gender differences. The DT resulted in a five-level model of significant factors affecting substance abuse relapse. These included lower cost for buying substances, lower age at first substance use, history of quitting substances without medication, frequency of substances utilization per month, and frequency of methadone therapy. Conclusions: Knowing the main factors associated with substance abuse relapse could be important for health care providers to make better decisions for improving the treatment outcomes of SRDs.