Mycobacterium species are slow growing bacteria that cause significant morbidity and mortality worldwide. Because of the relative rarity of mycobacterial infections, potential for detection of nonpathogenic environmental contaminants, and substantial costs associated with molecular diagnostics, effective screening methods are needed to identify samples most suitable for molecular testing. While anatomic pathology specimens can be utilized to identify characteristic histologic inflammatory patterns and to directly visualize mycobacteria through histochemical (acid fast bacilli [AFB]) stains, the utility of immunohistochemistry (IHC) in this setting is unknown. A cohort of 121 cases previously referred for mycobacterial sequencing, including 12 Mycobacterium tuberculosis (MTB), 42 nontuberculosis mycobacteria (NTM), and 67 cases negative for mycobacteria by polymerase chain reaction (PCR), were stained with an antimycobacteria antibody, and the results were compared with histology, AFB stains, PCR, and cultures. IHC was positive in 50% MTB, 81% NTM, and 49% of cases negative for mycobacteria by sequencing, with excellent (>90%) concordance with AFB stains. Organisms were identifiable by IHC using a 10× objective in the majority of cases. Negative PCR with positive IHC was attributed to paucity of organisms in 30/33 cases, and positive PCR with negative IHC was most often associated with MTB. IHC is highly sensitive for NTM but has a lower sensitivity for MTB, suggesting that cases with a high clinical and histologic suspicion for MTB should be sent for PCR even when AFB and IHC are negative. Incorporation of IHC into a screening algorithm for molecular testing has the potential for significant savings of cost and time.