Background Venous leg ulcers are common, chronic wounds that are painful and reduce quality of life. Compression therapy is known to assist in the healing of venous leg ulceration. Supervised exercise training that targets an improvement in calf muscle pump function might be a useful adjunctive therapy for enhancing ulcer healing and other aspects of physical and mental health. However, the evidence of exercise for individuals with venous ulcers is sparse. Here, we describe the protocol for a study that aims to assess the feasibility of undertaking a randomised controlled trial of a supervised exercise programme in people who are receiving compression for venous ulceration. Methods/Design This is a randomised, controlled, assessor-blinded, two-centre, feasibility trial with two parallel groups. Eighty adults who are receiving lower-limb compression for a venous leg ulcer will be randomly assigned to receive usual care (compression only) or usual care plus a 12-week supervised exercise programme. Participants in the exercise group will be invited to undertake three, 60-minute sessions of supervised exercise each week, and each session will involve a combination of treadmill walking, upright cycling and strength and flexibility exercises for the lower limbs. Participants will be assessed before randomisation and 3, 6 and 12 months after randomisation. Primary outcomes include rates of recruitment, retention and adherence. Secondary outcomes include time to ulcer healing, proportion of participants healed, percentage and absolute change in ulcer size, health-related quality of life (EQ-5D-5L and VEINES-QOL/Sym), lower-limb cutaneous microvascular function (laser Doppler flowmetry coupled with iontophoresis) and physical fitness (30-second sit-to-stand test, chair sit and reach test, 6-minute walk test and ankle range of motion). The costs associated with the exercise programme and health-care utilisation will be calculated. We will also complete interviews with a sub-sample of participants to explore their experiences of having a venous ulcer and the acceptability of the exercise intervention and study procedures. Discussion Data from this study will be used to refine the supervised exercise programme, investigate the acceptability of the intervention and study design and determine the most appropriate outcome measures, thereby providing estimates of the factors needed to design an adequately powered trial across several centres.