Although intercalating agents such as quinolones have had proven therapeutic success as antibacterial agents for more than 40 years, new forms of quinolone-based resistance in bacteria are continually emerging. To alleviate this problem, a new class of antibacterials is urgently needed; recently, novel bacterial topoisomerase inhibitors (NBTIs) have been found to be particularly important. Based on 67 experimentally evaluated NBTIs against wild-type (WT) DNA gyrase originating from Staphylococcus aureus, a predictive QSAR model was initially constructed and validated and was later used for in silico prediction of biological activities for an in house designed compound library of 548 novel drug-like NBTI combinatorial analogs. To evaluate the influence of gyrA alterations on NBTI resistance, various mutant homology models were constructed; meanwhile, their resistance profiles were assessed and validated relative to that of WT enzyme by structure-based virtual screening (VS) of known NBTIs. Surprisingly, the M121K mutant model was recognized as the most selective due to an additional established cation-π interaction between K121-NH3+ (not found in the WT) and the aromatic moiety of the NBTI right-hand site (RHS) fragment; this finding was additionally supported by VS of our combinatorially generated NBTIs. Moreover, we identified several attractive, synthetically feasible RHS building blocks that may enable the development of new NBTIs.