Veterans in treatment for substance use disorders (SUD) often report past criminal offending. However, the rate of criminal recidivism in this population is unknown. Further, prior research in veterans has not examined personality factors as predictors of recidivism, despite the prominence of such factors in leading models of recidivism risk management. We examined these issues in a secondary data analysis of 197 military veterans with a history of criminal offending who were enrolled in an SUD residential treatment program. Participants were interviewed using several measurement instruments at treatment entry, one month into treatment, treatment discharge, and 12 months post-discharge. Most veterans (94%) had a history of multiple charges, and 53% had recent involvement in the criminal justice system at the time of treatment entry. In the 12 months post-discharge, 22% reported reoffending. In addition, 30% of patients who had been recently involved in the criminal justice system at treatment entry reoffended during follow-up. Higher friend relationship quality (OR = 2.32, 95% CI [1.03, 5.21]) at treatment entry and higher staff ratings of patients' relationship quality with other residents during treatment (OR = 2.76, 95% CI [1.40, 5.41]) predicted lower odds of recidivism post-discharge. After accounting for these factors, smaller reductions during treatment in the personality trait of Negative Emotionality predicted an increased risk for criminal recidivism post-discharge (OR = 1.13, 95% CI [1.01, 1.26]). Results support augmenting the curriculum of SUD programs for veterans with services aimed at reducing risk for criminal recidivism, with a focus on interventions that directly target patients' social support networks and tendencies towards negative emotionality.