The P-glycoprotein (P-gp) efflux pump has an important role as a natural detoxification system in many types of normal and cancer cells. P-gp is implicated in multiple drug resistance (MDR) exhibited by several types of cancer against a multitude of anticancer chemotherapeutic agents, and therefore, it is clinically validated target for cancer therapy. Accordingly, in this study we combined exhaustive pharmacophore modeling and quantitative structure-activity relationship (QSAR) analysis to explore the structural requirements for potent P-gp inhibitors employing 130 known P-gp ligands. Genetic function algorithm (GFA) coupled with k nearest neighbor (kNN) or multiple linear regression (MLR) analyses were employed to build self-consistent and predictive QSAR models based on optimal combinations of pharmacophores and physicochemical descriptors. Successful pharmacophores were complemented with exclusion spheres to optimize their receiver operating characteristic curve (ROC) profiles. Optimal QSAR models and their associated pharmacophore hypotheses were validated by identification and experimental evaluation of new promising P-gp inhibitory leads retrieved from the National Cancer Institute (NCI) structural database. Several potent hits were captured. The most potent hit decreased the IC50 of doxorubicin from 0.906 to 0.190 μM on doxorubicin resistant MCF7 cell-line.