Diagnostic strategies to detect Mycobacterium avium subsp. paratuberculosis (MAP) super-shedder cows in dairy herds have been minimally studied. The objective of the current study was to compare the cost-effectiveness of strategies for identification of MAP super-shedders on a California dairy herd of 3,577 cows housed in free-stall pens. Eleven strategies that included serum or milk enzyme-linked immunosorbent assay (ELISA), quantitative real-time polymerase chain reaction (qPCR) or culture of environmental samples, pooled or individual cow fecal samples, or combinations thereof were compared. Nineteen super-shedders (0.5%) were identified by qPCR and confirmed by culture as cows shedding ≥ 10,000 colony forming units (CFU)/g feces (median of 30,000 CFU/g feces). A stratified random sample of the study herd based on qPCR results of fecal pools was the most sensitive (74%) strategy and had the highest cost ($5,398/super-shedder). The reference strategy with the lowest cost ($1,230/super-shedder) and sensitivity (47%) included qPCR testing of fecal samples from ELISA-positive lactating (milk) and nonlactating (serum) cows housed in pens with the highest MAP bioburden. The most cost-effective alternative to the reference was to perform qPCR testing of fecal samples from ELISA-positive cows (milk and serum for milking and dry cows, respectively) for a sensitivity of 68% and cost of $2,226/super-shedder. In conclusion, diagnostic strategies varied in their cost-effectiveness depending on the tests, specimen type, and labor costs. Initial qPCR testing of environmental samples from free-stall pens to target cows in pens with the highest MAP bioburden for further testing can improve the cost-effectiveness of strategies for super-shedder identification.