Although proteases are recognized as important virulent factors in pathogenic microorganisms, little information is available so far regarding the potential role of these enzymes in diseases caused by mycobacteria. Here we use bioinformatic tools to compare the protease-coding genes present in the genome of Mycobacterium leprae, Mycobacterium tuberculosis, Mycobacterium bovis and Mycobacterium avium paratuberculosis. This analysis allowed a review of the nomenclature of the protease family present in mycobacteria. A special attention was devoted to the 'decaying genome' of M. leprae where a relatively high level of conservation of protease-coding genes was observed when compared to other genes families. A total of 39 genes out of the 49 found in M. bovis were identified in M. leprae. Of relevance, a core of well-conserved 38 protease genes shared by the four species was defined. This set of proteases is probably essential for survival in the host and disease outcome and may constitute novel targets for drug development leading to a more effective control of mycobacterial diseases.