To evaluate the efficacy of a novel, multi-modal, preoperative approach to postprostatectomy penile rehabilitation (PR), we performed a retrospective review of patients who underwent nerve-sparing robotic-assisted laparoscopic prostatectomy (NS-RALP). All patients were evaluated at a comprehensive, academic sexual medicine clinic between 2016 and 2017. The "prehabilitation" PR group (n = 106) consisted of men who were seen in the pre-op period and began tadalafil and L-citrulline 2 weeks prior to surgery. Vacuum erectile device (VED) therapy was started at 1-month post-op. These interventions were continued throughout the 12-month follow-up period. Individuals refractory to these therapies could start treatment with intracavernosal injections. The postprostatectomy PR group (n = 25) consisted of men who were not seen in the pre-op period and started the above therapies immediately following their first visit. A higher percentage of men in the prehabilitation group reported return of erectile function within 12 months (56% vs. 24%, P = 0.007). The prehabilitation group also showed better compliance with PR (PDE5i [96% vs. 64%, P < 0.001], L-citrulline [93% vs. 49%, P < 0.001], and VED [55% vs. 20%, P < 0.001]). Seventy-eight percent of men who attended 4-5 follow-up visits reported return of erectile function. Our results suggest that men undergoing a preoperative protocol show superior recovery of erectile function following NS-RALP. Further studies with prospective designs are warranted.