Introduction Patient decision aids (PDAs) have been developed to help patients make an informed choice for a treatment option. Despite proven benefits, structural implementation falls short of expectations. The present study aims to assess the effectiveness and cost-utility of the PDA among newly diagnosed patients with localised prostate cancer and their partners, alongside implementation of the PDA in routine care. Methods/analysis A stepped-wedge cluster randomised trial will be conducted. The PDA will be sequentially implemented in 18 hospitals in the Netherlands, over a period of 24 months. Every 3 or 6 months, a new cluster of hospitals will switch from usual care to care including a PDA. The primary outcome measure is decisional conflict experienced by the patient. Secondary outcomes comprise the patient's quality of life, treatment preferences, role in the decision making, expectations of treatment, knowledge, need for supportive care and decision regret. Furthermore, societal cost-utility will be valued. Other outcome measures considered are the partner's treatment preferences, experienced participation to decision making, quality of life, communication between patient, partner and health care professional, and the effect of prostate cancer on the relationship, social contacts and their role as caregiver. Patients and partners receiving the PDA will also be asked about their satisfaction with the PDA. Baseline assessment takes place after the treatment choice and before the start of a treatment, with follow-up assessments at 3, 6 and 12 months following the end of treatment or the day after deciding on active surveillance. Outcome measures on implementation include the implementation rate (defined as the proportion of all eligible patients who will receive a PDA) and a questionnaire for health care professionals on determinants of implementing an innovation. Ethics and dissemination This study will be conducted in accordance with local laws and regulations of the Medical Ethics Committee of VU University Medical Center, Amsterdam, The Netherlands. The results from this stepped-wedge trial will be presented at scientific meetings and published in peer-reviewed journals. Trial registration Nederlands Trial Register NTR TC5177, registration date: May 28 th 2015.Pre-results.