Correct classification of herd infection status is a critical component of a program that designates herds as free of or low risk for paratuberculosis. The objective of this study was to determine cost-effective testing programs that provide high confidence of herd classification as paratuberculosis-free. A stochastic simulation model was developed to evaluate the testing program recommended by U.S. Voluntary Johne's Disease Herd Status Program, and alternative testing programs based on culture of pooled fecal samples, and environmental samples for initial testing. The initial model assumed that dairy herd remained closed, within-herd prevalence and the detection probability of testing method (DP) were constant over the period of testing (yearly repeated testing of test-negative herd). Herd-level negative predictive value (HPVN) and true prevalence of infected herds remained in the population after each round of herd testing were assessed to determine effectiveness of each testing program. In a population of 90 % infected herds with within-herd prevalence of 10%, initial testing with cultures of 5 environmental samples followed by repeated testing of all cows with pooled fecal cultures yielded HPVN of 0.19, 0.79, 0.94, and 0.98 with 43%, 15%, 5%, and 2% of the infected herds remaining in the test-negative population after the 1st, 2nd, 3rd, and 4th herd testing, respectively. In the same population, testing all cows with individual fecal culture after the initial testing of 30 cows with ELISA followed by fecal culture detected 100% of infected herds at the 3rd testing but with considerably higher cost. The model has been modified to account for incidence of new infections, dependence of sequential testing, variation of DP over the period of testing, variation of within-herd prevalence among the infected herds, which are the factors that strongly affect HPVN. Comparisons of HPVN among alternative testing programs, costs and model validation will be discussed.