Adeno-associated virus (AAV) vectors have achieved clinical efficacy in treating several diseases. However, enhanced vectors are required to extend these landmark successes to other indications and protein engineering approaches may provide the necessary vector improvements to address such unmet medical needs. To generate new capsid variants with potentially enhanced infectious properties and to gain insights into AAV’s evolutionary history, we computationally designed and experimentally constructed a putative ancestral AAV library. Combinatorial variations at 32 amino acid sites were introduced to account for uncertainty in their identities. We then analyzed the evolutionary flexibility of these residues, the majority of which have not been previously studied, by subjecting the library to iterative selection on a representative cell line panel. The resulting variants exhibited transduction efficiencies comparable to the most efficient extant serotypes and, in general, ancestral libraries were broadly infectious across the cell line panel, indicating that they favored promiscuity over specificity. Interestingly, putative ancestral AAVs were more thermostable than modern serotypes and did not use sialic acids, galactose or heparan sulfate proteoglycans for cellular entry. Finally, variants mediated 19- to 31-fold higher gene expression in the muscle compared with AAV1, a clinically used serotype for muscle delivery, highlighting their promise for gene therapy.