Background Mycobacterium avium subsp. paratuberculosis (MAP) causes Johne's disease (or paratuberculosis), a chronic wasting disease of ruminants and other animals resulting from granulomatous enteritis. There are increasing concerns that MAP is zoonotic. The prevalence of Johne's disease is increasing worldwide. In an attempt to control an epidemic of ovine Johne's disease (OJD) in New South Wales (NSW), a government/industry sponsored voluntary vaccination/onfarm management program commenced in 2000. We report herein an observational study of changes in disease prevalence as vaccination progressed, based on abattoir surveillance data for OJD from 1999 to 2009. We also discuss the epidemiological, policy, regulatory, research, economic and sociological elements that contributed to the development of a mature control program, whose aim was to halt the epidemic spread of OJD in a naïve sheep population. Methods NSW was divided into areas of "High"(HPA), "Medium"(MPA) and "Low"(LPA) OJD prevalence. A killed whole cell vaccine (Gudair®) was administered to sheep from 2000 to 2009. Trained examiners evaluated the viscera of adult sheep carcasses at slaughter for gross evidence of OJD. MAP infection was confirmed by histopathology. Principal findings From 2000-2009, 12 million vaccine doses were administered in NSW (91%; 10.9 million in the HPA). Many of the vaccinated flocks were suffering > 5% annual mortality in adult sheep, with some individual flocks with 10-15% losses attributable to OJD. A total of 7.6 million carcasses were examined (38%; 2.9 million from the HPA). Overall, 16% of slaughter consignments (sheep consigned to the abattoir from a single vendor) were positive for OJD, of which 94% were from the HPA. In the HPA, the percentage of animals with lesions attributable to OJD at slaughter fell progressively from 2.4% (10,406/432,860) at commencement of vaccination in 2000 to 0.8% (1,573/189,564) by 2009. Herd immunity from vaccination in the HPA was estimated at 70% by 2009, the target commonly espoused for an effective control program based on vaccination. This coincided with a progressive decrease in reports of clinical disease and mortalities in vaccinated flocks. Significance We show a decrease in the prevalence of lesions attributable to OJD in NSW concomitant with initiation of voluntary vaccination, on-farm management plans, abattoir monitoring and feedback of animal prevalence data to sheep producers. We conclude that a target of ≤1% regional prevalence of OJD affected sheep at slaughter is achievable using these interventions.