Rational design of improved gene delivery vehicles is a challenging and potentially time-consuming process. As an alternative approach, directed evolution can provide a rapid and efficient means for identifying novel proteins with improved function. Here we describe a methodology for generating very large, random adeno-associated viral (AAV) libraries that can be selected for a desired function. First, the AAV2 cap gene is amplified in an error-prone PCR reaction and further diversified through a staggered extension process. The resulting PCR product is then cloned into pSub2 to generate a diverse (>106) AAV2 plasmid library. Finally, the AAV2 plasmid library is used to package a diverse pool of mutant AAV2 virions, such that particles are composed of a mutant AAV genome surrounded by the capsid proteins encoded in that genome, which can be used for functional screening and evolution. This procedure can be performed in approximately 2 weeks.