The improvement of sensitivity and differentiation in rapidly identifying a small amount of mycobacteria in sputum has significant implications for reducing tuberculosis transmission. We previously applied the conventional PCR and capillary electrophoresis (CE) to establish the restriction fragment length polymorphism (RFLP) pattern of mycobacterial 65-kDa heat shock protein (hsp65) gene from colony specimens. However, the previous analysis did not provide enough sensitivity for sputum specimens in which the limitation of analysis might be hindered by PCR inhibitors and primer-dimers formation during amplification. In the current study, nested PCR (nPCR) had been redesigned for PCR-RFLP analysis (PRA) of mycobacterial hsp65 gene using CE. The results show both Mycobacterium tuberculosis complex and mycobacteria other than tuberculosis could be identified in the presence of PCR inhibitors. The interference due to primer-dimers was also minimized. Based on the Poisson distribution, the repeatability of single DNA molecule detection was greatly affected by sampling probability and might be improved significantly by increasing the sample loading. The PRA using nPCR and CE is not only able to detect the individual mycobacterial DNA molecule but also potentially differentiate the species.