The evolutionary battle between viruses and the immune system is essentially a high-stakes arms race. The immune system makes antiviral proteins, called restriction factors, which can stop the virus from replicating. In response, viruses evolve to evade the effects of restriction factors. To counter this, restriction factors evolve too, and the cycle continues, in which both sides rapidly evolve at interaction interfaces to gain or evade immune defense. For example, primate TRIM5α uses its rapidly evolving ‘v1’ loop to bind retroviral capsids whereas the MxA antiviral protein uses its rapidly evolving Loop L4 domain to recognize viruses such as influenza; single mutations in these loops can dramatically improve retroviral restriction. The challenge for the immune system is that mammals do not evolve as fast as viruses. How then, in the face of this disadvantage, can the immune system hope to keep pace with viral evolution? Using deep mutational scanning, we comprehensively measured how single mutations in the TRIM5α v1 loop affect restriction of divergent retroviruses. Unexpectedly, we found that most mutations increase weak antiviral function. Moreover, most random mutations do not disrupt potent viral restriction, even when it is newly acquired via a single adaptive substitution. Our results indicate that TRIM5α’s adaptive landscape is remarkably broad and mutationally resilient, maximizing its chances of success in evolutionary arms races with retroviruses. We also exploit combinatorial mutagenesis at rapidly evolving positions to dissect and enhance the antiviral properties of MxA antiviral proteins, revealing unprecedented capacity for antiviral adaptation and a 'breath versus specificity' tradeoff that constrains their natural evolution.