Background: Increased physical activity (PA) is crucial for achieving and maintaining glycemic control and is beneficial for overall well-being of patients with type 2 diabetes as well. Despite that, many patients fail to make changes in their exercise behavior. Self-determination theory (SDT) addresses this problem and suggests that perceived autonomy support, autonomous motivation and self-care competence play a key role in the process of health behavior change. This study investigated the impact of these three factors on success in increasing PA among patients with type 2 diabetes but considered also the role of other important life-context factors, such as mental health, stress and social support. The effect of these other factors may outweigh the effect of SDT constructs; however, previous studies based on SDT have largely overlooked them. Methods: This cross-sectional mail survey was carried out in 2011. Out of 2866 respondents, those who had been over 2 years in care in their present and principal primary care health center and had during the past two years tried to increase PA either with or without success (n = 1256, mean age 63 years, 52% men), were included in this study. Logistic regression and mediation analyses were the main methods used in the data analysis. Results: Autonomous motivation predicted success in increasing PA even after controlling for the effect of other important life-context factors. Other predictors of success were felt energy, good perceived health, younger age and less social support. Autonomous motivation mediated the effect of perceived autonomy support from a doctor on success in increasing PA. Conclusion: The results were in line with SDT showing the importance of autonomous motivation for success in increasing PA. Doctor-patient relationships and lifestyle interventions should focus on promoting self-motivated reasons for health behavior change.