Protein-protein interactions (PPIs) are prospective but challenging targets for drug discovery, because screening using traditional small-molecule libraries often fails to identify hits. Recently, we developed a PPI-oriented library comprising 12,593 small-to-medium-sized newly synthesized molecules. This study validates a promising combined method using PPI-oriented library and ligand-based virtual screening (LBVS) to discover novel PPI inhibitory compounds for Kelch-like ECH-associated protein 1 (Keap1) and nuclear factor erythroid 2-related factor 2 (Nrf2). We performed LBVS with two random forest models against our PPI library and the following time-resolved fluorescence resonance energy transfer (TR-FRET) assays of 620 compounds identified 15 specific hit compounds. The high hit rates for the entire PPI library (estimated 0.56-1.3%) and the LBVS (maximum 5.4%) compared to a conventional screening library showed the utility of the library and the efficiency of LBVS. All the hit compounds possessed novel structures with Tanimoto similarity ≤ 0.26 to known Keap1/Nrf2 inhibitors and aqueous solubility (AlogP < 5). Reasonable binding modes were predicted using 3D alignment of five hit compounds and a Keap1/Nrf2 peptide crystal structure. Our results represent a new, efficient method combining the PPI library and LBVS to identify novel PPI inhibitory ligands with expanded chemical space.