A cross-sectional analysis of stored Ziehl-Neelsen (ZN)-stained sputum smear slides (SSS) obtained from two public tuberculosis referral laboratories located in Juiz de Fora, Minas Gerais, was carried out to distinguish Mycobacterium bovis from other members of the Mycobacterium tuberculosis complex (MTC). A two-step approach was used to distinguish M. bovis from other members of MTC: (i) oxyR pseudogene amplification to detect MTC and, subsequently, (ii) allele-specific sequencing based on the polymorphism at position 285 of this gene. The oxyR pseudogene was successfully amplified in 100 of 177 (56.5%) SSS available from 99 individuals. No molecular profile of M. bovis was found. Multivariate analysis indicated that acid-fast bacilli (AFB) results and the source laboratory were associated (p < 0.05) with oxyR pseudogene amplification. SSS that were AFB++ SSS showed more oxyR pseudogene amplification than those with AFB0, possibly due to the amount of DNA. One of the two source laboratories presented a greater chance of oxyR pseudogene amplification, suggesting that differences in sputum conservation between laboratories could have influenced the preservation of DNA. This study provides evidence that stored ZN-SSS can be used for the molecular detection of MTC.