Antiviral proteins often evolve rapidly at virus-binding interfaces to defend against new viruses. We investigated whether antiviral adaptation via missense mutations might face limits, which insertion or deletion mutations (indels) could overcome. We report one such case of a nearly insurmountable evolutionary challenge: the human anti-retroviral protein TRIM5α requires more than five missense mutations in its specificity-determining v1 loop to restrict a divergent simian immunodeficiency virus (SIV). However, duplicating just one amino acid in v1 enables human TRIM5α to potently restrict SIV in a single evolutionary step. Moreover, natural primate TRIM5α v1 loops have evolved indels that confer novel antiviral specificities. Thus, indels enable antiviral proteins to overcome viral challenges inaccessible by missense mutations, revealing the potential of these often-overlooked mutations in driving protein innovation.