Insertions and deletions (InDels) are essential sources of novelty in protein evolution. In RNA viruses, InDels cause dramatic phenotypic changes contributing to the emergence of viruses with altered immune profiles and host engagement. This work aimed to expand our current understanding of viral evolution and explore the mutational tolerance of RNA viruses to InDels, focusing on Enterovirus A71 (EV-A71) as a prototype for Enterovirus A species (EV-A). Using newly described deep InDel scanning approaches, we engineered approximately 45,000 insertions and 6,000 deletions at every site across the viral proteome, quantifying their effects on viral fitness. As a general trend, most InDels were lethal to the virus. However, our screen reproducibly identified a set of InDel-tolerant regions, demonstrating our ability to comprehensively map tolerance to these mutations. Tolerant sites highlighted structurally flexible and mutationally plastic regions of viral proteins that avoid core structural and functional elements. Phylogenetic analysis on EV-A species infecting diverse mammalian hosts revealed that the experimentally-identified hotspots overlapped with sites of InDels across the EV-A species, suggesting structural plasticity at these sites is an important function for InDels in EV speciation. Our work reveals the fitness effects of InDels across EV-A71, identifying regions of evolutionary capacity that require further monitoring, which could guide the development of Enterovirus vaccines.