In order to successfully enhance exercise motivation and behaviour change, it is of particular importance to explore and understand theoretical mechanisms underpinning exercise behaviours. Research based on adequate theory and using appropriate mediating variable analyses (MVA) could inform practice by identifying the active ingredients of successful exercise promotion intervention designs and distinguishing elements that could (or should) be excluded. Such an approach could not only promote cost-effectiveness, but also contribute to the understanding of sustainable behavior change and provide valuable practical implications for intervention design. This study aimed to examine the abovementioned mechanisms based on Self-Determination Theory (SDT; Deci & Ryan, 1985; 2000). Adult active members of an Internet-based exercise program (n = 1,091) between 18 and 78 years of age completed a test battery including the Basic Psychological Needs in Exercise Scale (BPNES); the Behavioural Regulation in Exercise Questionnaire-2 (BREQ-2) and Leisure Time Exercise Questionnaire (LTEQ). Data was analysed by structural equation modelling (SEM) and mediation analyses using bootstrapping resampling approach. Mplus version 7.1 was used to analyse the data with the maximum likelihood (ML) and robust maximum likelihood (MLM) estimators. Need satisfaction was found to predict self-determined motivation, which in turn predicted exercise, especially for women. Self-determined motivation mediated the association between need satisfaction and exercise, and these associations were moderated by gender and age. The results highlight the potential impact of considering moderating effects for a better understanding of how and for whom exercise interventions could influence behavioural outcomes. Future research would benefit practice by further exploration of underlying mechanisms in terms of mediating and moderating effects in order to be able to make adequate recommendations on how to tailor SDT intervention designs, e.g. by addressing age and gender issues.