Sortase A is a virulence factor responsible for the attachment of surface proteins to Staphylococcus aureus and other Gram-positive bacteria. Inhibitors of this enzyme are potential anti-infective agents. Herein, a new highly selective magnetic relaxation-based method for screening potential sortase A inhibitors is described. A 13-amino acid-long peptide substrate of sortase A is conjugated to SiO2-EDTA-Gd NPs. In the presence of sortase A, the LPXTG motif on the peptide strand is cleaved resulting in a shortened peptide as well as a reduced water T2 value whose magnitude is dependent on the concentration of sortase A. The detection limit is determined to be 76 pM. In contrast, the presence of sortase A inhibitors causes the T2 to remain at a higher value. The proposed method is used to characterize inhibition of sortase A by curcumin and 4-(hydroxymercuri)benzoic acid with an IC50 value of 12.9 ± 1.6 μM and 130 ± 1.76 μM, respectively. Furthermore, this method was successfully applied to detect sortase A activity in bacterial suspensions. The feasibility to screen different inhibitors in Escherichia coli and S. aureus suspensions was demonstrated. This method is fast and potentially useful to rapidly screen possible inhibitors of sortase A in bacterial suspensions, thereby aiding in the development of antibacterial agents targeting Gram-positive bacteria.