Enteroaggregative Escherichia coli (EAEC) is an increasingly recognized pathogen associated with acute and persistent diarrhea worldwide. While EAEC strains are considered highly heterogeneous, aggregative adherence fimbriae (AAFs) are thought to play a pivotal role in pathogenicity by facilitating adherence to the intestinal mucosa. In this study, we optimized an existing multiplex PCR to target all known AAF variants, which are distinguished by differences in their pilin subunits. We applied the assay on a collection of 162 clinical Danish EAEC strains and interestingly found six, by SNP analysis phylogenetically distinct, strains harboring the major pilin subunits from both AAF/III and AAF/V. Whole-genome and plasmid sequencing revealed that in these six strains the agg3A and agg5A genes were located on a novel pAA plasmid variant. Moreover, the plasmid also encoded several other virulence genes including some not previously found on pAA plasmids. Thus, this plasmid endows the host strains with a remarkably high number of EAEC associated virulence genes hereby likely promoting strain pathogenicity.