Gram-positive bacteria, in general, and staphylococci, in particular, are the widespread cause of nosocomial and community-acquired infections. The rapid evolvement of strains resistant to antibiotics currently in use is a serious challenge. Novel antimicrobial compounds have to be developed to fight these resistant bacteria, and sortase A, a bacterial cell wall enzyme, is a promising target for novel therapies. As a transpeptidase that covalently attaches various virulence factors to the cell surface, this enzyme plays a crucial role in the ability of bacteria to invade the host’s tissues and to escape the immune response. In this study we have screened a small molecule library against recombinant Staphylococcus aureus sortase A using an in vitro FRET-based assay. The selected hits were validated by NMR methods in order to exclude false positives and to analyze the reversibility of inhibition. Further structural and functional analysis of the best hit allowed the identification of a novel class of benzisothiazolinone-based compounds as potent and promising sortase inhibitors.