G-protein-coupled receptors (GPCRs) are key signaling molecules and are intensely studied. Whereas GPCRs recognizing small-molecules have been successfully targeted for drug discovery, protein-recognizing GPCRs, such as the chemokine receptors, claim few drugs or even useful small molecule reagents. This reflects both the difficulties that attend protein-protein interface inhibitor discovery, and the lack of structures for these targets. Imminent structure determination of chemokine receptor CXCR4 motivated docking screens for new ligands against a homology model and subsequently the crystal structure. More than 3 million molecules were docked against the model and then against the crystal structure; 24 and 23 high-scoring compounds from the respective screens were tested experimentally. Docking against the model yielded only one antagonist, which resembled known ligands and lacked specificity, whereas the crystal structure docking yielded four that were dissimilar to previously known scaffolds and apparently specific. Intriguingly, several were potent and relatively small, with IC(50) values as low as 306 nM, ligand efficiencies as high as 0.36, and with efficacy in cellular chemotaxis. The potency and efficiency of these molecules has few precedents among protein-protein interface inhibitors, and supports structure-based efforts to discover leads for chemokine GPCRs.