The limitations of conventional methods of identification of Mycobacterium tuberculosis have led to the development of several nucleic acid amplification techniques which have the advantage of being rapid, sensitive, and specific. However, their expense or the need for technical expertise makes it difficult to use them in regions in which tuberculosis is endemic. A novel PCR restriction analysis (PRA) of the hsp65 gene was therefore developed for rapid screening of clinical isolates to identify Mycobacterium spp. The restriction enzymes NruI and BamHI were selected to obtain a limited number of restriction patterns to further differentiate between Mycobacterium tuberculosis complex (MTBC) and nontuberculous mycobacteria (NTM). Three hundred ten isolates from clinical specimens and 24 reference strains were tested. The assay correctly identified 295 of the 310 culture isolates as MTBC, while the remaining 15 isolates were identified as NTM. Of the isolates tested, 135 MTBC strains and all 15 NTM were also confirmed by PRA using Sau96I and CfoI. Thirty-eight randomly selected MTBC strains and all 15 NTM were further confirmed by sequencing. The NruI/BamHI PRA was simple, as it did not require any elaborate analyses. It was cost-effective, rapid, highly sensitive, and specific and did not require technical expertise. The assay can, therefore, be used as a simple screening test not only to detect Mycobacterium spp. but also to differentiate MTBC from NTM in peripheral laboratories with minimal availability of funds.