The increasing prevalence of N. gonorrhoeae strains exhibiting decreased susceptibility to third-generation cephalosporins and the recent isolation of two distinct strains with high-level resistance to cefixime or ceftriaxone heralds the possible demise of β-lactam antibiotics as effective treatments for gonorrhea. To identify new compounds that inhibit penicillin-binding proteins (PBPs), which are proven targets for β-lactam antibiotics, we developed a high-throughput assay that uses fluorescence polarization (FP) to distinguish the fluorescent penicillin, Bocillin-FL, in free or PBP-bound form. This assay was used to screen a 50,000 compound library for potential inhibitors of N. gonorrhoeae PBP 2, and 32 compounds were identified that exhibited >50% inhibition of Bocillin-FL binding to PBP 2. These included a cephalosporin that provided validation of the assay. After elimination of compounds that failed to exhibit concentration-dependent inhibition, the antimicrobial activity of the remaining 24 was tested. Of these, 7 showed antimicrobial activity against susceptible and penicillin- or cephalosporin-resistant strains of N. gonorrhoeae. In molecular docking simulations using the crystal structure of PBP 2, two of these inhibitors docked into the active site of the enzyme and each mediate interactions with the active site serine nucleophile. This study demonstrates the validity of a FP-based assay to find novel inhibitors of PBPs and paves the way for more comprehensive high-throughput screening against highly resistant strains of N. gonorrhoeae. It also provides a set of lead compounds for optimization of anti-gonococcal agents.