Assembly of pili in Gram-positive bacteria and their attachment to the cell wall envelope are mediated by sortases. In Bacillus cereus and its close relative Bacillus anthracis, the major pilin protein BcpA is cleaved between the threonine and the glycine of its C-terminal LPXTG motif sorting signal by the pilin-specific sortase D. The resulting acyl enzyme intermediate is relieved by the nucleophilic attack of the side-chain amino group of lysine within the YPKN motif of another BcpA subunit. Cell wall anchoring of assembled BcpA pili requires sortase A, which also cleaves the LPXTG sorting signal of BcpA between its threonine and glycine residues. We show here that sortases A and D require only the C-terminal sorting signal of BcpA for substrate cleavage. Unlike sortase D, which accepts the YPKN motif as a nucleophile, sortase A forms an amide bond between the BcpA C-terminal carboxyl group of threonine and the side-chain amino group of diaminopimelic acid within the cell wall peptidoglycan of bacilli. These results represent the first demonstration of a cell wall anchor structure for pili, which are deposited by sortase A into the envelope of many different microbes.