Paired samples of formalin-fixed, paraffin-embedded ileum and lymph node from 204 culled dairy cows were investigated for evidence of infection by Mycobacterium avium subsp. paratuberculosis. Of the samples, 151 were from animals that were tissue-culture positive for M. avium subsp. paratuberculosis, and 53 were from animals that were tissue and fecal culture negative. From the culture-positive animals, M. avium subsp. paratuberculosis was isolated from 78 samples of ileum and from 107 samples of lymph node. Ziehl-Neelsen acid-fast and immunoperoxidase stained slides were examined for 15 minutes each. Acid-fast organisms were identified in 7 of 78 (8.97%) and 6 of 106 (5.61%) culture-positive ileum and lymph node samples, respectively. Immunohistochemical (IHC) analysis of the same tissues identified infection in the ileum of 9 of 78 (11.54%) and in the lymph node of 5 of 106 (4.67%) culture-positive tissues. All tissues from culture-negative animals tested negative when using acid-fast and IHC staining. The sensitivity of these 2 tests in detecting M. avium subsp. paratuberculosis in culled dairy cows was not significantly different, and the tests exhibited substantial to almost perfect agreement. Both tests were much less sensitive than bacterial culture, detecting less than 6% of tissues positive compared with culture.