Type IV pili (T4P) are critical to virulence for Vibrio cholerae and other bacterial pathogens. Among their diverse functions, T4P mediate microcolony formation, which protects the bacteria from host defences and concentrates secreted toxins. The T4P of the two V. cholerae O1 disease biotypes, classical and El Tor, share 81% identity in their TcpA subunits, yet these filaments differ in their interaction patterns as assessed by electron microscopy. To understand the molecular basis for pilus-mediated microcolony formation, we solved a 1.5 A resolution crystal structure of N-terminally truncated El Tor TcpA and compared it with that of classical TcpA. Residues that differ between the two pilins are located on surface-exposed regions of the TcpA subunits. By iteratively changing these non-conserved amino acids in classical TcpA to their respective residues in El Tor TcpA, we identified residues that profoundly affect pilus:pilus interaction patterns and bacterial aggregation. These residues lie on either the protruding d-region of the TcpA subunit or in a cavity between pilin subunits in the pilus filament. Our results support a model whereby pili interact via intercalation of surface protrusions on one filament into depressions between subunits on adjacent filaments as a means to hold V. cholerae cells together in microcolonies.