Certification-and-monitoring programs for paratuberculosis are based on repetitive herd testing to establish a herd's health status. The available tests have poor sensitivity. Infected but undetected herds may remain among certified 'paratuberculosis-free' herds. Our objective was to determine if truly free herds acquire a certified status and keep it over time when infected but undetected herds remain. The Dutch program was used as a basis to construct a mechanistic deterministic model of the evolution over 25 years of the number of herds per health status. Three health states for herds were defined: not detected as infected in the certification process to obtain a free status; not detected as infected by any of the repetitive tests for monitoring the certified free status; detected as infected. Among undetected herds, two types were defined: truly free vs. undetected but infected. Transitions between states were due to the purchase of an infected animal, infection via the environment, clearance via culling or sales, detection of an infected animal, and certification. A sensitivity analysis was carried out. We showed that - for a 100% specific test only - most of the truly free herds at the beginning of the program got a certified free status and kept it over time. Most infected herds were either detected as infected or cleared. The number of certified truly free herds increased with a decrease in the animal-level prevalence or in the risk of purchasing an infected cattle, for example by restricting purchases to cattle from herds at the highest level of certification.