When advising farmers on how to control Johne's disease in an infected herd, one of the main recommendations is to avoid feeding waste milk to calves and instead feed calf milk replacer (CMR). This advice is based on the assumption that CMR is free of viable Mycobacterium avium ssp. paratuberculosis (MAP) cells, an assumption that has not previously been challenged. We tested commercial CMR products (n = 83) obtained from dairy farms around the United States by the peptide-mediated magnetic separation (PMS)-phage assay, PMS followed by liquid culture (PMS-culture), and direct IS900 quantitative PCR (qPCR). Conventional microbiological analyses for total mesophilic bacterial counts, coliforms, Salmonella, coagulase-negative staphylococci, streptococci, nonhemolytic Corynebacterium spp., and Bacillus spp. were also performed to assess the overall microbiological quality of the CMR. Twenty-six (31.3%) of the 83 CMR samples showed evidence of the presence of MAP. Seventeen (20.5%) tested positive for viable MAP by the PMS-phage assay, with plaque counts ranging from 6 to 1,212 pfu/50 mL of reconstituted CMR (average 248.5 pfu/50 mL). Twelve (14.5%) CMR samples tested positive for viable MAP by PMS-culture; isolates from all 12 of these samples were subsequently confirmed by whole-genome sequencing to be different cattle strains of MAP. Seven (8.4%) CMR samples tested positive for MAP DNA by IS900 qPCR. Four CMR samples tested positive by both PMS-based tests and 5 CMR samples tested positive by IS900 qPCR plus one or other of the PMS-based tests, but only one CMR sample tested positive by all 3 MAP detection tests applied. All conventional microbiology results were within current standards for whole milk powders. A significant association existed between higher total bacterial counts and presence of viable MAP indicated by either of the PMS-based assays. This represents the first published report of the isolation of viable MAP from CMR. Our findings raise concerns about the potential ability of MAP to survive manufacture of dried milk-based products.