Purpose: Strategies to improve pre-operative cardiopulmonary fitness could positively impact recovery after surgery. This study investigated the feasibility of vigorous intensity aerobic interval exercise in bladder cancer patients prior to radical cystectomy (RC). Methods: A total of 60 patients were randomised (1:1) to exercise or control following a cardiopulmonary exercise test (CPET). The exercise group was offered twice-weekly pre-operative supervised vigorous intensity aerobic interval exercise in addition to standard treatment. The controls received standard treatment only. A repeat CPET was undertaken before surgery and post-operative recovery outcomes were recorded. Results: Over half of the 112 eligible patients approached in the clinic were recruited to the study (53.5%), with recruited patients attending a median of 8 (range 1–10) exercise sessions over a pre-operative period of 3–6 weeks. Improvements in peak values of oxygen pulse (P = 0.001), minute ventilation (P = 0.002) and power output (P < 0.001) were observed at the follow-up CPET in the exercise group versus controls and there were no adverse events. Although this feasibility study was not powered to detect changes in post-operative recovery outcomes, there were marginal (non-significant) differences in favour of the exercise group in post-operative Clavien-Dindo score and need for high dependency unit inotropic support. Conclusions: Bladder cancer patients respond well to pre-surgical aerobic interval exercise, and the improvements in cardiopulmonary fitness variables could have important implications for post-operative recuperation after RC. These findings provide a strong foundation for an adequately powered randomised controlled trial.