Mycobacteroides abscessus (M. ab) infections are innately resistant to most currently available antibiotics and present a growing, poorly addressed medical need. The existing treatment regimens are lengthy and produce inadequate outcomes for many patients. Importantly, most clinically used drugs and drug candidates against M. ab are either bacteriostatic, or only weakly bactericidal. New strategies exploring a broader chemical space are urgently needed, as innovative agents in development are scarce and hit rates in large unbiased screens against the mycobacterium have been discouragingly low. Here we present a computational chemogenomics-driven approach to discovery of novel antibacterials that effectively reveals drug-like compounds active against M. ab, paired with small sets of predicted molecular targets for the compounds. Several of the bioactive hits identified exhibited rapid bactericidal, including sterilizing, activity against the mycobacterium, indicating that there are currently unexploited chemically tractable molecular mechanisms for rapid sterilization of M. ab. Interestingly, starvation, which typically induces drug tolerance, sensitized M. ab to some of the compounds, resulting in potencies similar to those of drugs in clinical use. The presented drug discovery platform has potential to identify highly differentiated prototype anti-infective molecules and thereby contribute to development of regimens for shorter treatment and improved outcomes for non-tuberculous mycobacterial infections.