Objective: In this study, the associations between the substitution of sedentary time with sleep or physical activity at different intensities and subsequent weight-loss maintenance were examined. Methods: This prospective study included 1152 adults from the NoHoW trial who had achieved a successful weight loss of ≥5% during the 12 months prior to baseline and had BMI ≥25 kg/m² before losing weight. Physical activity and sleep were objectively measured during a 14-day period at baseline. Change in body weight was included as the primary outcome. Secondary outcomes were changes in body fat percentage and waist circumference. Cardiometabolic variables were included as exploratory outcomes. Results: Using isotemporal substitution models, no associations were found between activity substitutions and changes in body weight or waist circumference. However, the substitution of sedentary behavior with moderate-to-vigorous physical activity was associated with a decrease in body fat percentage during the first 6 months of the trial (−0.33% per 30 minutes higher moderate-to-vigorous physical activity [95% CI: −0.60% to −0.07%], p = 0.013). Conclusions: Sedentary behavior had little or no influence on subsequent weight-loss maintenance, but during the early stages of a weight-loss maintenance program, substituting sedentary behavior with moderate-to-vigorous physical activity may prevent a gain in body fat percentage.