Sortases anchor surface proteins to the cell wall of Gram-positive pathogens through recognition of specific motif sequences. Loss of sortase leads to large reductions in virulence, which identifies sortase as a target for the development of antibacterials. By screening 135,625 small molecules for inhibition, we report here that aryl (beta-amino)ethyl ketones inhibit sortase enzymes from staphylococci and bacilli. Inhibition of sortases occurs through an irreversible, covalent modification of their active site cysteine. Sortases specifically activate this class of molecules via beta-elimination, generating a reactive olefin intermediate that covalently modifies the cysteine thiol. Analysis of the three-dimensional structure of Bacillus anthracis sortase B with and without inhibitor provides insights into the mechanism of inhibition and reveals binding pockets that can be exploited for drug discovery.