Meditopes are cyclic peptides that bind in a specific pocket in the antigen-binding fragment of a therapeutic antibody such as cetuximab. Provided their moderate affinity can be enhanced, meditope peptides could be used as specific non-covalent and paratope-independent handles in targeted drug delivery, molecular imaging, and therapeutic drug monitoring. Here we show that the affinity of a recently reported meditope for cetuximab can be substantially enhanced using a combination of yeast display and deep mutational scanning. Deep sequencing was used to construct a fitness landscape of this protein-peptide interaction, and four mutations were identified that together improved the affinity for cetuximab 10-fold to 15 nM. Importantly, the increased affinity translated into enhanced cetuximab-mediated recruitment to EGF receptor-overexpressing cancer cells. Although in silico Rosetta simulations correctly identified positions that were tolerant to mutation, modeling did not accurately predict the affinity-enhancing mutations. The experimental approach reported here should be generally applicable and could be used to develop meditope peptides with low nanomolar affinity for other therapeutic antibodies.