To evaluate the diagnostic performance of a whole-body 18F-choline (FCH) hybrid PET/MRI for prostate cancer patients at biochemical relapse after radical prostatectomy (RP) compared to pelvic multiparametric MRI (mpMRI), one of the standard imaging modality for this patient population. From 2010 to 2016, 58 whole-body FCH PET/MRI studies with mpMRI acquisitions were performed in 53 prostate cancer patients relapsing after curative RP. Median PSA and PSA doubling time (PSA DT) at PET study were 1.5 ng/ml and 6.5 months, respectively. The overall positivity rate of FCH PET/MRI was 58.6% (n = 34), dropping to 44% in patients with a PSA ≤ 2 ng/ml (n = 36). Median PSA values in positive and negative PET/MRI studies were 2.2 ng/ml and 0.8 ng/ml, respectively, with no differences in PSA DT (6.5 vs. 6.6 months). A PSA value ≥ 1.5 ng/ml was a significant predictor of positivity on PET/MRI studies. Compared to PET, mpMRI identified more local relapses (17 vs. 14, p = 0.453) while PET outperformed whole-body Dixon MRI for regional (16 vs. 9, p = 0.016) and distant (12 vs. 6, p = 0.031) metastases. Compared to pelvic mpMRI, the treatment approach turned out to be influenced more frequently using whole-body FCH hybrid PET/MRI studies (58.6% vs. 38%). In prostate cancer patients with biochemical recurrence after RP, whole-body FCH PET/MRI achieved a higher detection rate of nodal/distant metastases compared to pelvic mpMRI alone, increasing the change of treatment strategy by more than 20%.