Control over supramolecular recognition between proteins and nanoparticles (NPs) is of fundamental importance in therapeutic applications and sensor development. Most NP-protein binding approaches use 'tags' such as biotin or His-tags to provide high affinity; protein surface recognition provides a versatile alternative strategy. Generating high affinity NP-protein interactions is challenging however, due to dielectric screening at physiological ionic strengths. We report here the co-engineering of nanoparticles and protein to provide high affinity binding. In this strategy, 'supercharged' proteins provide enhanced interfacial electrostatic interactions with complementarily charged nanoparticles, generating high affinity complexes. Significantly, the co-engineered protein-nanoparticle assemblies feature high binding affinity even at physiologically relevant ionic strength conditions. Computational studies identify both hydrophobic and electrostatic interactions as drivers for these high affinity NP-protein complexes.