Previous research showed that goal setting messages (i.e., messages indicating how to pursue a recommended goal) and vested interest messages (i.e., messages on the hedonic relevance of a behaviour) may induce an increase in healthy behaviour. In the present study, we examined whether such messages (and their combination) are effective in promoting regular physical activity, compared to a control condition. We also explored whether message persuasiveness would vary according to receivers’ Body Mass Index (BMI). A sample of 448 Italian volunteers participated in a 1-month messaging intervention through the PsyMe app. Results showed that all messages increased physical activity. These effects were still present at follow-up (one month after the end of the intervention). Interestingly, as BMI increased combined (goal setting + vested interest) messages were more persuasive than goal setting or vested interest messages alone, suggesting that receivers with higher body weight need more information on how and why achieving a regular physical activity goal. These results advance our comprehension of the effects of messages aimed at promoting regular physical activity.