Purpose: This study assessed the feasibility and acceptability of an online mindfulness-based intervention (MBI) for people diagnosed with melanoma. The potential benefit of the MBI on fear of cancer recurrence (FCR), worry, rumination, perceived stress and trait mindfulness was also explored. Methods: Participants who have completed treatment for stage 2c or 3 melanoma were recruited from an outpatient clinic and randomly allocated to either the online MBI (intervention) or usual care (control). The 6-week online MBI comprised short videos, daily guided meditations and automated email reminders. Participants were asked to complete questionnaires at baseline and at 6-week post-randomisation. Study feasibility and acceptability were assessed through recruitment rates, retention and participant feedback. Clinical and psychosocial outcomes were compared between groups using linear mixed models. Results: Sixty-nine (58%) eligible participants were randomised (46 in the intervention; 23 in the control group); mean age was 53.4 (SD 13.1); 54% were female. Study completion rate across both arms was 80%. The intervention was found helpful by 72% of the 32 respondents. The intervention significantly reduced the severity of FCR compared to the control group (mean difference = − 2.55; 95% CI − 4.43, − 0.67; p = 0.008). There was no difference between the intervention and control groups on any of the outcome measures. Conclusions: This online MBI was feasible and acceptable by people at high risk of melanoma recurrence. It significantly reduced FCR severity in this sample. Patients valued accessing the program at their own pace and convenience. This self-guided intervention has the potential to help survivors cope with emotional difficulties. An adequately powered randomised controlled trial to test study findings is warranted.