Objectives: The objective of this study is to investigate the efficacy of psychological Interventions – Mindfulness or Implementation Intention – associated with a Physical Activity program, delivered via internet, in reducing Multiple Sclerosis symptoms. Method: Thirty-five adults were randomly assigned to one of the three groups: a Mindfulness-Based Intervention group (N = 12), Implementation Intention group (N = 11), and a Control Group (N = 12). All the groups received the same Physical Activity program. The Mindfulness condition group received daily training in the form of pre-recorded sessions while the Implementation group elaborated their specific plans once a week. Mobility, fatigue, and the impact of the disease on the patient’s life were measured. Two measurement times are carried out in pre-post intervention, at baseline and after eight weeks. Results: Overall, after 8 weeks intervention, results show that there was a significant increase in Walking distance in the three groups. In addition, the within-group analysis showed a statistically significant improvement between pre and post intervention on the physical component of the Disease Impact scale in the Implementation Intention group (p = 0.023) with large effect size, in the Mindfulness-Based Intervention group (p = 0.008) with a medium effect size and in the control group (p = 0.028) with small effect size. In the Implementation Intention group, all physical, psychosocial and cognitive Fatigue Impact subscales scores decreased significantly (p = 0.022, p = 0.023, and p = 0.012, respectively) and the physical component was statistically and negatively correlated (r = −0.745; p = 0.008) when Implementation Intention group practice a mild to moderate physical activity. In the Mindfulness-Based Intervention group, the physical component (MFIS) showed a statistically significant improvement (p = 0.028) but no correlation with moderate-to-vigorous physical activity (MVPA); the control group outcomes did not reveal any significant change. Conclusion: The results of this study are very encouraging and show the feasibility of Mindfulness interventions associated with physical activity to improve the health of people with MS. Further study should assess Mindfulness interventions tailored to MS condition and using both hedonic and eudemonic measures of happiness.