Two decontamination chemicals, hexadecylpyridinium choride (HPC) and N-acetyl-L-cysteine-sodium hydroxide (NALC-NaOH), were compared for their efficacy of reducing the growth of non-specific microorganisms in milk while minimally affecting the recovery of Mycobacterium avium subsp. paratuberculosis (MAP). In addition three culture mediums, Bactec 12B and Trek-ESP para-JEM, and Herrold’s egg yolk media (HEYM), were compared for the ability to suppress growth of non-specific microorganisms as well as their sensitivity of detection of low levels of MAP in milk. Results indicated that exposing the milk to 1.5% NALC-NaOH for 15 minutes most effectively reduced nontarget microorganisms without reducing MAP viability. In addition, the Bactec 12B medium detected the lowest levels of MAP more rapidly and more consistently than the other two mediums.