Crystal structures of two homologous peptidases from cyanobacteria Anabaena variabilis and Nostoc punctiforme at 1.05 Å and 1.60 Å resolution represent the first structures of a large class of cell-wall, cysteine peptidases that contain an N-terminal bacterial SH3-like domain (SH3b) and a C-terminal NlpC/P60 cysteine peptidase domain. The NlpC/P60 domain is a primitive, papain-like peptidase in the CA clan of cysteine peptidases with a Cys126/His176/His188 catalytic triad and a conserved catalytic core. We deduced from structure and sequence analysis, and then experimentally, that that these two proteins act as γ-D-glutamyl-L-diamino acid endopeptidases (EC 3.4.22.-). The active site is located near the interface between the SH3b and NlpC/P60 domains, where the SH3b domain may help define substrate specificity, instead of functioning as a targeting domain, so that only muropeptides with an N-terminal L-alanine can bind to the active site.