The bacterial type IIA topoisomerases, DNA gyrase and topoisomerase IV, are essential enzymes that control the topological state of DNA during replication and validated antibacterial drug targets. Growing resistance against fluoroquinolones, that also target these enzymes, limits their therapeutic potential and stimulates the search for novel inhibitor classes targeting their ATP-binding sites. Starting from a library of marine alkaloid oroidin analogs, we identified low micromolar inhibitors of E. coli DNA gyrase, based on the 5,6,7,8-tetrahydroquinazoline and 4,5,6,7-tetrahydrobenzo[1,2-d]thiazole scaffolds. Structure-based optimization of the initial hits resulted in low nanomolar E. coli DNA gyrase inhibitors, some of which exhibited micromolar inhibition of E. coli topoisomerase IV and of S. aureus homologs. Studies of the binding modes of inhibitors in the ATP-binding sites of the E. coli DNA gyrase support the observed structure-activity relationship. Some of the compounds possessed modest antibacterial activity against Gram positive bacterial strains, while their evaluation against wild-type, impA and ΔtolC E. coli strains suggests that they are efflux pump substrates and/or do not possess the physico-chemical properties necessary for cell wall penetration. Our study provides a rationale for optimization of this class of compounds towards balanced dual DNA gyrase and topoisomerase IV inhibitors with antibacterial activity.