Although behavioral weight-loss interventions produce short-term weight loss, long-term maintenance remains elusive. This randomized trial examined whether learning a novel set of "stability skills" before losing weight improved long-term weight management. Stability skills were designed to optimize individuals current satisfaction with lifestyle and self-regulatory habits while requiring the minimum effort and attention necessary. Overweight/obese women (N = 267) were randomly assigned to one of two 6-month interventions and assessed at baseline and at 6, 12, and 18 months. Maintenance First women participated first in an 8-week stability skills maintenance module and then in a standard 20-week behavioral weight-loss program. Weight Loss First women participated first in a standard 20-week behavioral weight-loss program and then in a standard 8-week problem-solving skills maintenance module. There was no intervention staff contact during the 12-month follow-up period (6-18 months). As designed, Maintenance First participants lost the same percentage of initial weight during the 6-month intervention period as Weight Loss First participants (M = -8.6%, SD = 5.7, vs. M = -9.1%, SD = 6.9; t = -0.6, p = .52). However, Maintenance First participants regained significantly less weight during the 12-month follow-up period (6-18 months) than Weight Loss First participants (M = 3.2 lb, SD = 10.4, vs. M = 7.3 lb, SD = 9.9 [M = 1.4 kg, SD = 4.7, vs. M = 3.3 kg, SD = 4.5]; t = 3.3, p = .001, d = 0.4). Learning stability skills before losing weight was successful in helping women to maintain weight loss without intervention staff contact during follow-up. These results can inform the study design of future innovative interventions.