Surface proteins attached by sortases to the cell wall envelope of bacterial pathogens play important roles during infection. Sorting and attachment of these proteins is directed by C-terminal signals. Sortase B of S. aureus recognizes a motif NPQTN, cleaves the polypeptide after the Thr residue, and attaches the protein to pentaglycine cross-bridges. Sortase B of B. anthracis is thought to recognize the NPKTG motif, and attaches surface proteins to m-diaminopimelic acid cross-bridges. We have determined crystal structure of sortase B from B. anthracis and S. aureus at 1.6 and 2.0 A resolutions, respectively. These structures show a beta-barrel fold with alpha-helical elements on its outside, a structure thus far exclusive to the sortase family. A putative active site located on the edge of the beta-barrel is comprised of a Cys-His-Asp catalytic triad and presumably faces the bacterial cell surface. A putative binding site for the sorting signal is located nearby.