Recovery approaches to health care now feature in the mental health policies of many Western countries. There are, however, continuing challenges to the operationalization of these approaches. This study aimed to identify the nature of these challenges for a public mental health service organization located in a major urban center in southeastern Australia, where Recovery-oriented services have been implemented; and to develop recommendations to address these challenges. These aims were achieved by asking mental health consumers about their experiences of the implementation of Recovery-oriented services. Research participants described an uncertainty in health professionals and consumers alike about how to practice within a Recovery model, with many health professionals taking a "hands off" approach in the name of Recovery, rather than working in partnership with consumers and other stakeholders, including the community managed organizations. Solutions to these challenges included more targeted, practice-focused education for consumers and health professionals, with this education provided by consumer representatives. Insights derived from this research add to the growing body of evidence related to the implementation of Recovery-oriented services in Western countries.