To identify optimal method(s) for certification and subsequent monitoring of Mycobacterium avium subsp. paratuberculosis (Map)-unsuspected herds, certification-and-monitoring schemes were studied using a stochastic simulation model ("JohneSSim"). JohneSSim simulated the within-herd transmission and economic aspects of Map in closed Dutch dairy herds. The model was validated with field observations on Map-unsuspected herds. The current Dutch certification-and-monitoring schemes were compared with 11 alternative schemes in which individual and pooled fecal culture, ELISA, Johnin-intradermal test and gamma-IFN ELISA were used, varying the test frequency, tested age group and number of tested animals. On reaching the 'Map-free' status with the standard certification scheme, 11% of the simulated herds were not truly Map-free. Therefore, the designation 'Map-free' should be changed into, for instance, 'low-risk Map'. In the most-attractive alternative certification scheme, the 'Map-free' status was reached after four herd examinations (at 2-year intervals) consisting of serial testing of all cattle > or = 2 years of age with a pooled fecal culture and individual fecal culture of positive pools. This scheme resulted in lower total and annual discounted costs and a lower animal-level prevalence at reaching the 'Map-free' status compared to the standard scheme, assuming that there was no new introduction of the infection. Schemes to monitor the 'Map-free' status were compared, assuming that this status was reached with the standard certification scheme. In comparison to the standard monitoring scheme, none of the alternative monitoring schemes resulted in both a lower animal-level prevalence of undetected pre-existing Map infections in closed herds, and lower median annual discounted costs. Results of the model were very sensitive to the assumed sensitivity of the fecal culture test and to management measures that prevent within-herd transmission of Map. If these preventive measures were taken, the probability of undetected Map infections in closed 'Map-free' herds was decreased substantially.