Mycobacterium avium subsp. paratuberculosis (MAP) is the etiological agent of Johne's disease in ruminants and a probable pathogen of Crohn's disease in humans. Accurate, cost-effective, and time-relevant diagnostics are the basis for efficient control programs. This study was conducted as an attempt to re-evaluate MAP detection improvement by coupling solid media enrichment to a more specific IS900 conventional PCR and a very specific F57/IC real-time PCR. In a spiking experiment, we investigated the improvement of molecular-based MAP detection in feces after a culture-based enrichment step into Herrold's egg yolk media with mycobactin J (HEYM-MJ) for different time intervals, when compared to traditional culture. Detection limit of culture was 0.33 × 10(4) bacteria × g(-1) (33 CFU g(-1)), while that of IS900 PCR when coupled with an enrichment step for 2, 4, and 6 weeks was 0.33 × 10(5) (0.33 × 10(3) CFU g(-1)), 0.33 × 10(4) (33 CFU g(-1)), and 33 (>3.3 CFU g(-1)) bacteria × g(-1), respectively. Whereas the detection limits of F57/IC real-time PCR after the enrichment step for the same time intervals were 0.33 × 10(5) (0.33 × 10(3) CFU g(-1)), 0.33 × 10(3) (3.3 CFU g(-1)), and 33 (>3.3 CFU g(-1)) bacteria × g(-1), respectively. Altogether, enrichment of bovine fecal samples into solid media increased the sensitivity of specific molecular detection of MAP using IS900 conventional PCR and duplex F57/IC real-time PCR and offers an expedited and accurate alternative for MAP detection in bovine feces. Validation of these results is further recommended using field bovine fecal samples.