Uptake of decision aids (DAs) in daily routine is low, resulting in limited knowledge about successful DA implementation at a large scale. We assessed implementation rates after multi-regional implementation of three different prostate cancer (PCa) treatment DAs and patient-perceived barriers and facilitators to use a DA. Thirty-three hospitals implemented one out of the three DAs in routine care. Implementation rates for each DA were calculated per hospital. After deciding about PCa treatment, patients (n = 1033) completed a survey on pre-formulated barriers and facilitators to use a DA. Overall DA implementation was 40%. For each DA alike, implementation within hospitals varied from incidental (< 10% of eligible patients receiving a DA) to high rates of implementation (> 80%). All three DAs were evaluated positively by patients, although concise and paper DAs yielded higher satisfaction scores compared with an elaborate online DA. Patients were most satisfied when they received the DA within a week after diagnosis. Pre-formulated barriers to DA usage were experienced by less than 10% of the patients, and most patients confirmed the facilitators. Many patients received a DA during treatment counseling, although a wide variation in uptake across hospitals was observed for each DA. Most patients were satisfied with the DA they received. Sustained implementation of DAs in clinical routine requires further encouragement and attention.