Objective: To determine the feasibility and efficacy of a physical activity behavioural change intervention in managing cancer-related fatigue among gynaecological cancer survivors during and post anti-cancer treatments. Methods: A two arm, single blind, randomised controlled trial was conducted within the Northern Ireland regional Cancer Centre. Thirty three sedentary gynaecological cancer survivors (stage I-III; = 3 years post diagnosis), experiencing cancer-related fatigue (mild-severe) took part. Participants were randomly assigned to a behavioural change, moderate intensity physical activity intervention (n = 16) or a Contact Control group (n = 17). The primary outcome was fatigue (Multidimensional Fatigue Symptom Inventory-Short Form and Functional Assessment in Chronic Illness Therapy-Fatigue subscale). Secondary outcomes included quality of life, physical functioning, positive and negative affect, depression, body composition, sleep dysfunction and self-reported physical activity. Feasibility was assessed based on the recruitment rate, programme and physical activity adherence and participants' programme evaluation, including optional focus groups (n = 16). Results: Twenty five percent of eligible women took part (33/134). Participants were 8.7 (SD = 9.1) months post diagnosis, with a mean age of 53 (SD = 10.3) years. The majority of the sample had a diagnosis of ovarian (n = 12) or endometrial cancer (n = 11). Significant differences favouring the intervention group were observed for fatigue at 12 weeks and 6 months follow-up (12 week: mean difference = -11.06; 95% confidence interval (CI) = -21.89 to - 0.23; effect size (d) = 0.13; p = 0.046; 6 month: mean difference = -19.48; 95% CI = - 19.67 to - 19.15; effect size (d) = 0.20; p = 0.01). A mean of 10 calls (SD = 1.2 calls) were delivered to the Physical Activity Group, and 10 (SD = 1.6 calls) to the CC group. The intervention was positively perceived based on exit questionnaire and focus group findings. Conclusions: A physical activity behavioural change intervention for gynaecological cancer survivors is feasible in terms of participants' programme adherence and evaluation, and the intervention demonstrates improvements in fatigue. However, confirmation in the form of a larger fully powered RCT is warranted.