A stochastic model was developed to assess the risk of introduction of Mycobacterium paratuberculosis infection into a dairy herd through purchase of replacement females. Effects of infection prevalence in the source herd(s) and use of ELISA alone or ELISA and fecal culture as risk mitigation strategies also were evaluated. A hypothetical dairy herd, free from M. paratuberculosis, which replaced 30 (1 lot) of its cows per year, was considered. Probability distributions were estimated for the sensitivities and specificities of ELISA and fecal culture, the proportion of infected herds and within-herd prevalence for a randomly-selected replacement source herds (high prevalence) and herds in level-3 of the Voluntary Johnes Disease Herd Status Program (low prevalence). For the initial model assumptions that the ELISA sensitivity was 45%, simulation results predicted that 1% to 10% of the M. paratuberculosis-infected lots would not be detected by the ELISA. The negative predictive value (NPV) (the probability that given the total lot-test result is negative, all the animals in the lot are truly not infected) ranged from 77% for ELISA results to 83% for fecal culture, if the lot was comprised of animals purchased from high prevalence (randomly-selected) herds. On the other hand, the NPVs were both 99%, for lots of cattle purchased from low-prevalence (level-3) herds. The benefit of testing introduced cattle with ELISA alone or in combination with fecal culture was minimal if cows were purchased from known, low-prevalence (level-3) herds. The value of testing by ELISA alone or in combination with fecal culture increased greatly in high-prevalence herds. Testing of random-source replacement females can partially mitigate the risk of introduction of M. paratuberculosis, but not as well as by using test-negative herds as the source, with or without testing.