Perfluorooctanesulfonate (PFOS) persistently accumulates in the environment and in humans, causing various toxicities. To determine the key molecular determinants for optimal PFOS specificity and efficiency, we designed and synthesized a combinatorial gold nanoparticle (GNP) library consisting of 18 members with rationally diversified hydrophobic, electrostatic, and fluorine-fluorine interaction components for PFOS bindings. According to our findings, the electrostatic and F-F interactions between PFOS and nanoparticles are complementary. When F-F attractions are relatively weak, the electrostatic interactions are dominant. As F-F interactions increase, the electrostatic contributions are reduced to as low as 20%, demonstrating that F-F binding may overpower even electrostatic interactions. Furthermore, F-F interactions (28-79% binding efficiency) are 2-fold stronger than regular hydrophobic interactions (15-39% binding efficiency) for PFOS adsorption, explaining why these novel PFOS-binding nanoparticles are superior to other conventional materials based on either hydrophobic or electrostatic binding. The PFOS adsorption by the optimized nanoparticles performs well in the presence of ionic interferences and in environmental wastewater. This library mapping approach can potentially be applied to recognition mechanism investigation of other pollutants and facilitate the discovery of effective monitoring probes and matrices for their removal.