Bacteria communicate and collectively regulate gene expression using a process called quorum sensing (QS). QS relies on group-wide responses to signal molecules called autoinducers. Here, we show that QS activates a new program of multicellularity in Vibrio cholerae. This program, which we term aggregation, is distinct from the canonical surface-biofilm formation program, which QS represses. Aggregation is induced by autoinducers, occurs rapidly in cell suspensions, and does not require cell division, features strikingly dissimilar from those characteristic of V. cholerae biofilm formation. Extracellular DNA limits aggregate size, but is not sufficient to drive aggregation. A mutagenesis screen identifies genes required for aggregate formation, revealing proteins involved in V. cholerae intestinal colonization, stress response, and a protein that distinguishes the current V. cholerae pandemic strain from earlier pandemic strains. We suggest that QS-controlled aggregate formation is important for V. cholerae to successfully transit between the marine niche and the human host.