Fatty acid-binding protein 4 (FABP4, AFABP) is a potential drug target for diabetes and atherosclerosis. In this study, a series of novel FABP4 inhibitors were discovered through combining virtual screening and substructure search. Seventeen compounds exhibited FABP4 inhibitory activities with IC50 < 10 μM, among which 11 compounds showed high selectivity against FABP3. The best compound 36b displayed an IC50 value of 1.5 μM. Molecular docking and point mutation studies revealed that Gln95, Arg126, and Tyr128 play key roles for these compounds binding with FABP4. Interestingly, Gln95 seems to be essential for conformation stability of FABP4. The new scaffolds of these compounds and their interaction mechanisms binding with FABP4 should provide an important clue for the further development of novel FABP4 inhibitors.