Objective To test the feasibility of a telephone delivered intervention, informed by cognitive behavioural principles, for post-stroke fatigue, and estimated its effect on fatigue and other outcomes. Design Randomised controlled parallel group trial. Setting Three Scottish stroke services. Subjects Stroke survivors with fatigue three months to two years post-stroke onset. Interventions Seven telephone calls (fortnightly then a ‘booster session’ at 16 weeks) of a manualised intervention, plus information about fatigue, versus information only. Main measures Feasibility of trial methods, and collected outcome measures (fatigue, mood, anxiety, social participation, quality of life, return to work) just before randomisation, at the end of treatment (four months after randomisation) and at six months after randomisation. Results Between October 2018 and January 2020, we invited 886 stroke survivors to participate in postal screening: 188/886 (21%) returned questionnaires and consented, of whom 76/188 (40%) were eligible and returned baseline forms; 64/76 (84%) returned six month follow-up questionnaires. Of the 39 allocated the intervention, 23 (59%) attended at least four sessions. At six months, there were no significant differences between the groups (adjusted mean differences in Fatigue Assessment Scale −0.619 (95% CI −4.9631, 3.694; p = 0.768), the Generalised Anxiety Disorder 7 −0.178 (95% CI −3.823, 3.467, p = 0.92), and the Patient Health Questionnaire −0.247 (95% CI −2.935, 2.442, p = 0.851). There were no between-group differences in quality of life, social participation or return to work. Conclusion Patients can be recruited to a trial of this design. These data will inform the design of further trials in post-stroke fatigue.