Australian health workforce regulation is premised on the need to protect public health and safety. Specific criteria are set out by governments to ascertain the degree of risk and the need for government intervention. A study was undertaken to understand the current state of usage and the practice of naturopathy and western herbal medicine, and to ascertain whether statutory regulation was warranted. We found increased use of these complementary therapies in the community, with risks arising from both the specific practices as well as consumers negotiating a parallel primary health care system. We also found highly variable standards of training, a myriad of professional associations, and a general failure of current systems of self-regulation to protect public health and safety. Statutory regulation was the preferred policy response for consumers, insurers, general practitioners, and most of the complementary therapists. While we found a case for statutory registration, we also argue that a minimalist regulatory response needs to be accompanied by other measures to educate the public, to improve the standards of practice, and to enhance our understanding of the interaction between complementary and mainstream health care.