Dutch dairy herds can obtain a 'Mycobacterium avium subsp. paratuberculosis (Map) free' status after serial testing of all cattle >= 3 yr. with an ELISA and fecal culture, followed by four annual pooled fecal cultures of all cattle >= 2 yr. with negative results only. However, this certification scheme was felt to be too expensive, especially for closed herds. Therefore, alternative certification schemes were studied using a stochastic simulation model. The model, called 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 scheme was compared with nine alternative test schemes in which the individual and pooled fecal culture, ELISA, Johnin intradermal test and gamma-interferon ELISA were employed, varying the test frequency, tested age group and number of tested animals. In the most attractive alternative certification scheme, the 'Map free' status was reached after four herd examinations, at two-year intervals, consisting of serial testing of all cattle >= 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 prevalence at reaching the 'Map free' status compared to the current scheme, assuming that there was no new introduction of the infection. However, with none of the certification schemes, all simulated herds were truly 'Map free' on reaching the 'Map free' status. The ensuing risk of transmission of Map between 'Map free' herds was studied separately. 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 infections. If these preventive measures were taken, the probability of undetected Map infections in closed 'Map free' herds was substantially decreased.