Mycobacterium avium subsp. paratuberculosis (MAP) is the causative agent of Johne’s disease which induces chronic and fatal intestinal disorder in ruminants. MAP isolation from fecal samples is often difficult because of the slow growth bacteria that usually take long incubation time when using standard culture method. To improve MAP recovery from fecal samples, we developed an immunomagnetic separation (IMS) assay using chicken anti-MAP IgY. A diagnostic assay using immunomagnetic separation was developed to capture MAP from bovine feces by means of IgY derived from chicken eggs. The antibody was coupled directly onto the surface of magnetic nanoparticles by being mixed with magnetic nanoparticles and chicken antibodies. Analytical sensitivity and specificity were determined by extracting DNA from the captured MAP and amplifying it by IS900 PCR. The immunomagnetic separation capture followed by PCR (IMS-PCR) based on the IS900 element was evaluated in this study and showed a detection threshold corresponding to 20 cells/g in MAP-spiked fecal sample. In contrast, DNA extracted with heat treatment showed low detection efficiency of MAP-spiked fecal sample. No PCR inhibition was observed with DNA from the organisms captured with use of the nanoparticle-IgY beads. Thus, we revealed that this IMS-PCR method is particularly well adapted to the detection of MAP in fecal samples with rapid and reliable results.