Acknowledging the need for the development of fast and sensitive bacterial detection methods, we functionalized superparamagnetic iron oxide nanoparticles to identify Mycobacterium avium spp. paratuberculosis (MAP), through magnetic relaxation. Our results indicate that the MAP nanoprobes (1) bind specifically to MAP, (2) can quantify the bacterial target quickly in milk and blood with high sensitivity, and (3) are not susceptible to interferences caused by other bacteria. The use of the described magnetic nanosensors in the identification and quantification of bacteria in clinical and environmental samples is anticipated.