Abattoir surveillance for ovine paratuberculosis or Johne’s disease monitoring in Australia has provided valuable feedback to producers about their flock’s disease status since its commencement in 1999. The current surveillance system relies on the identification of gross lesions in sheep carcases at an abattoir, followed by sampling and histopathology testing. This manual inspection system has not been adapted to meet the changing disease situation, as infection prevalence levels have declined over time, due to the use of long-term vaccination. This simulation study compares the current system with two alternative approaches utilising a validated quantitative (q)PCR method for the detection of Mycobacterium avium subsp. paratuberculosis in tissues, with random systematic sampling either alone or in conjunction with sampling of a single carcass presenting gross lesions. Consigned sheep were randomly simulated as either infected or uninfected according to defined prevalence levels of infection, with varying histopathological lesion severity and the presence or absence of gross lesions. These sheep were then allocated into multiple ‘lines’ (group of sheep slaughtered together) within each consignment, with each line subjected to testing with the three sampling strategies for the estimation of line and flock (consignment) sensitivity. The line sensitivity described the proportion of infected lines that tested positive, whereas the flock sensitivity was the proportion of consignments from the simulated infected flocks that had one or more lines test positive for paratuberculosis infection. The MAP tissue qPCR strategy with gross lesion detection achieved marginally higher line sensitivity than the current abattoir surveillance strategy. The simulation of unvaccinated infected flocks with low to moderate prevalence levels demonstrated similar flock sensitivity for all three sampling models. However, the current strategy had very low line sensitivity for the simulated vaccinated infected flocks, when the infection prevalence level was <2%. There were substantial differences in flock sensitivity between the two tissue qPCR approaches and the current abattoir surveillance strategy for vaccinated infected flocks, whereas, only marginal differences in flock sensitivity were evident between the two tissue qPCR models. Our results demonstrate that the current strategy is not effective at identifying infected animals at very low infection prevalence levels. The MAP tissue qPCR approach investigated in this study is better as it removes the reliance on meat inspectors to identify suspected OJD gross lesions and can assist in identifying flocks that have subclinical infected sheep not displaying gross lesions. Therefore, the sheep industry may benefit from incorporating the MAP tissue qPCR for OJD surveillance, however the logistics (sampling approaches, time and costs) of conducting this type of testing need to be considered prior to implementing any changes.