The aim of this study was to compare a web-based computer tailored physical activity intervention based on self-determination theory and motivational interviewing (I Move) to a traditional web-based computer tailored physical activity intervention (Active Plus) with regard to their basic psychological need supporting capabilities. We also aimed to assess the extent to whether self-determination constructs played a stronger mediating role in the effects of I Move than in the effects of Active Plus. A randomized controlled trial was conducted among 3089 participants (age 44.9 ± 12.9, 69.1% women), comparing 1) I Move, 2) Active Plus, and 3) a waiting list control condition. Physical activity behavior (measured at baseline, and at six months after baseline), potential mediators (intrinsic motivation, identified regulation, perceived competence and perceived choice, measured at baseline, and at three months after baseline) and basic psychological need support (measured six weeks and six months after baseline) were assessed through self-report, using web-based questionnaires. I Move was found to be more effective in supporting participants' basic psychological needs (sessions 1 and 2; p = .001; sessions 3 and 4; p = .004). The results of the mediation analyses show that the effects of both interventions were (equally) mediated by perceived competence, but not by intrinsic motivation, identified regulation or perceived choice.