Despite over 100 years of study, the intestinal pathogen Vibrio cholerae still causes epidemic disease in areas of the world where there is poor sanitation. While cholera toxin and the toxin-coregulated pilus (TCP) are known to be essential for full virulence, the role that other factors play has remained ill-defined. Herein, we describe a large-scale signature-tagged mutagenesis (STM) screen utilizing 100 pools of 96 mutants each to identify factors involved in colonization of the infant mouse small intestine. A total of 164 mutants representing transposition events into 95 different open reading frames were shown to be recovered at greatly reduced numbers from the infant mouse model. Analysis of the sites of insertion revealed multiple independent mutations within the rfb gene cluster, needed for synthesis of lipopolysaccharide (LPS), and the tcp gene cluster, needed for synthesis of the TCP. More importantly, in addition to these previously known colonization factors, we identified many genes whose activity in colonization was not previously appreciated. These can be divided into a number of functional groups, which include production of factors involved in metabolic activities, regulation of cellular processes, transport, adaptation to stress and unknown functions. In addition, we describe the reiterative use of STM, whereby colonization-defective mutants were assembled into virulence-attenuated pools (VAPs), which were used to begin to reveal roles that the identified virulence factors play in the infection process. Nine new factors were shown to be crucial for the V. cholerae acid tolerance response, which has previously been hypothesized to be important for epidemic spread of cholera. Competition assays of these nine acid tolerance response (ATR)-defective mutants revealed that mutations in gshB, hepA and recO result in a 1000-fold reduction in colonization.