Due to the inherently flexible nature of a protein-protein interaction surface, it is difficult both to inhibit the association with a small molecule, and to predict how it might bind to the surface. In this study, we have examined small molecules that mediate the interaction between a WWI motif on the C-helix of HIV-1 glycoprotein-41 (gp41) and a deep hydrophobic pocket contained in the interior N-helical trimer. Association between these two components of gp41 leads to virus-cell and cell-cell fusion, which could be abrogated in the presence of an inhibitor that binds tightly in the pocket. We have studied a comprehensive combinatorial library of α-helical peptidomimetics, and found that compounds with strongly hydrophobic side chains had the highest affinity. Computational docking studies produced multiple possible binding modes due to the flexibility of both the binding site and the peptidomimetic compounds. We applied a transferred paramagnetic relaxation enhancement experiment to two selected members of the library, and showed that addition of a few experimental constraints enabled definitive identification of unique binding poses. Computational docking results were extremely sensitive to side chain conformations, and slight variations could preclude observation of the experimentally validated poses. Different receptor structures were required for docking simulations to sample the correct pose for the two compounds. The study demonstrated the sensitivity of predicted poses to receptor structure and indicated the importance of experimental verification when docking to a malleable protein-protein interaction surface.