Sortases are cysteine transpeptidases that assemble surface proteins and pili in their cell envelope. Encoded by all Grampositive bacteria, few Gram-negative bacteria and archaea, sortases are currently divided into six classes (A-F). Due to the steep increase in bacterial genome data in recent years, the number of sortase homologues have also escalated rapidly. In this study, we used protein sequence similarity networks to explore the taxonomic diversity of sortases and also to evaluate the current classification of these enzymes. The resultant data suggest that sortase classes A, B, and D predominate in Firmicutes and classes E and F are enriched in Actinobacteria, whereas class C is distributed in both Firmicutes and Actinobacteria except Streptomyces family. Sortases were also observed in various Gram-negatives and euryarchaeota, which should be recognized as novel classes of sortases. Motif analysis around the catalytic cysteine was also performed and suggested that the residue at 2nd position from cysteine may help distinguish various sortase classes. Moreover, the sequence analysis indicated that the catalytic arginine is highly conserved in almost all classes except sortase F in which arginine is replaced by asparagine in Actinobacteria. Additionally, class A sortases showed higher structural variation as compared to other sortases, whereas inter-class comparisons suggested structures of class C and D2 exhibited best similarities. A better understanding of the residues highlighted in this study should be helpful in elucidating their roles in substrate binding and the sortase function, and successively could help in the development of strong sortase inhibitors.