Background Sexual dysfunction is common in patients with either ischaemic heart disease (IHD) or implantable cardioverter defibrillator (ICD) and has a negative impact on quality of life. Non-pharmacological treatment options are lacking. The purpose of this trial was to assess the effect of sexual rehabilitation versus usual care for males with erectile dysfunction and either IHD and/or ICD. Methods Participants with erectile dysfunction and IHD and/or ICD were randomised to 12 weeks of sexual rehabilitation consisting of physical exercise training, pelvic floor exercise and psychoeducation, or usual care. Primary outcome: Sexual function by the International Index of Erectile Function (IIEF). Secondary outcome: Sexual function by the Psychosocial Adjustment to Illness Scale. Exploratory outcomes: Exercise capacity, pelvic floor strength/endurance, self-reported health and mental health. Results 154 participants were included, mean age 61.6 years (SD 6.1). Sexual rehabilitation compared with usual care improved sexual function with a mean difference IIEF score of 6.7 (95% CI 3.1 to 10.4, p<0.0003) at 4 months between groups (unadjusted IIEF mean scores 36.4 vs 31.3) and a mean difference of 6.7, 95% CI 3.2 to 10.1 (p<0.0002) at 6 months between groups (unadjusted mean scores IIEF 37.1 vs 32.2). No effects were seen on the secondary outcome. Sexual rehabilitation improved exercise capacity on cycle ergometer measured by Watt max with a mean difference of 10.3, 95% CI 3.6 to 16.9 (p<0.003) and pelvic floor strength (p<0.01). No differences were seen on self-reported health and mental health. Conclusion Sexual rehabilitation compared with usual care improves sexual function and exercise capacity.