Enteroaggregative Escherichia coli (EAEC) is a leading cause of acute and persistent diarrhea worldwide. A recently emerged Shiga-toxin-producing strain of EAEC resulted in significant mortality and morbidity due to progressive development of hemolytic-uremic syndrome. The attachment of EAEC to the human intestinal mucosa is mediated by aggregative adherence fimbria (AAF). Using X-ray crystallography and NMR structures, we present new atomic resolution insight into the structure of AAF variant I from the strain that caused the deadly outbreak in Germany in 2011, and AAF variant II from archetype strain 042, and propose a mechanism for AAF-mediated adhesion and biofilm formation. Our work shows that major subunits of AAF assemble into linear polymers by donor strand complementation where a single minor subunit is inserted at the tip of the polymer by accepting the donor strand from the terminal major subunit. Whereas the minor subunits of AAF have a distinct conserved structure, AAF major subunits display large structural differences, affecting the overall pilus architecture. These structures suggest a mechanism for AAF-mediated adhesion and biofilm formation. Binding experiments using wild type and mutant subunits (NMR and SPR) and bacteria (ELISA) revealed that despite the structural differences AAF recognize a common receptor, fibronectin, by employing clusters of basic residues at the junction between subunits in the pilus. We show that AAF-fibronectin attachment is based primarily on electrostatic interactions, a mechanism not reported previously for bacterial adhesion to biotic surfaces.