We developed a stochastic simulation model to compare the herd sensitivity (HSe) of five testing strategies for detection of Mycobacterium avium subsp. paratuberculosis (Map) in Midwestern US dairies. Testing strategies were ELISA serologic testing by two commercial assays (EA and EB), ELISA testing with follow-up of positive samples with individual fecal culture (EAIFC and EBIFC), individual fecal culture (IFC), pooled fecal culture (PFC), and culture of fecal slurry samples from the environment (ENV). We assumed that these dairies had no prior paratuberculosis-related testing and culling. We used cost-effectiveness (CE) analysis to compare the cost to HSe of testing strategies for different within-herd prevalences. HSe was strongly associated with within-herd prevalence, number of Map organisms shed in feces by infected cows, and number of samples tested. Among evaluated testing methods with 100% herd specificity (HSp), ENV was the most cost-effective method for herds with a low (5%), moderate (16%) or high (35%) Map prevalence. The PFC, IFC, EAIFC and EBIFC were increasingly more costly detection methods. Culture of six environmental samples per herd yielded >or=99% HSe in herds with >or=16% within-herd prevalence, but was not sufficient to achieve 95% HSe in low-prevalence herds (5%). Testing all cows using EAIFC or EBIFC, as is commonly done in paratuberculosis-screening programs, was less likely to achieve a HSe of 95% in low than in high prevalence herds. ELISA alone was a sensitive and low-cost testing method; however, without confirmatory fecal culture, testing 30 cows in non-infected herds yielded HSp of 21% and 91% for EA and EB, respectively.