Background: Enteroaggregative Escherichia coli (EAEC) are defined by their stacked-brick adherence pattern to human epithelial cells. There is no all-encompassing genetic marker for EAEC. The category is commonly implicated in diarrhea but research is hampered by perplexing heterogeneity. Methodology/Principal Findings: To identify key EAEC lineages, we applied multilocus sequence typing to 126 E. coli isolates from a Nigerian case-control study that showed aggregative adherence in the HEp-2 adherence assay, and 24 other EAEC strains from diverse locations. EAEC largely belonged to the A, B1 and D phylogenetic groups and only 7 (4.6%) isolates were in the B2 cluster. As many as 96 sequence types (STs) were identified but 60 (40%) of the EAEC strains belong to or are double locus variants of STs 10, 31, and 394. The remainder did not belong to predominant complexes. The most common ST complex, with predicted ancestor ST10, included 32 (21.3%) of the isolates. Significant age-related distribution suggests that weaned children in Nigeria are at risk for diarrhea from of ST10-complex EAEC. Phylogenetic group D EAEC strains, predominantly from ST31- and ST394 complexes, represented 38 (25.3%) of all isolates, include genome-sequenced strain 042, and possessed conserved chromosomal loci. Conclusions/Significance: We have developed a molecular phylogenetic framework, which demonstrates that although grouped by a shared phenotype, the category of 'EAEC' encompasses multiple pathogenic lineages. Principal among isolates from Nigeria were ST10-complex EAEC that were associated with diarrhea in children over one year and ECOR D strains that share horizontally acquired loci.