Enteroaggregative Escherichia coli (EAEC) organisms belong to a diarrheagenic pathotype known to cause diarrhea and can be characterized by distinct aggregative adherence (AA) in a stacked-brick pattern to cultured epithelial cells. In this study, we investigated 118 EAEC strains isolated from the stools of Danish adults with traveler's diarrhea. We evaluated the presence of the aggregative adherence fimbriae (AAFs) by a multiplex PCR, targeting the four known major subunit variants as well as their usher-encoding genes. Almost one-half (49/118) of the clinical isolates did not possess any known AAF major fimbrial subunit, despite the presence of other AggR-related loci. Further investigation revealed the presence of an AAF-related gene encoding a yet-uncharacterized adhesin, termed agg5A. The sequence of the agg5DCBA gene cluster shared fimbrial accessory genes (usher, chaperone, and minor pilin subunit genes) with AAF/III, as well as the signal peptide present in the beginning of the agg3A gene. The complete agg5DCBA gene cluster from a clinical isolate, EAEC strain C338-14, with the typical stacked-brick binding pattern was cloned, and deletion of the cluster was performed. Transformation to a nonadherent E. coli HB101 and complementation of the nonadherent C338-14 mutant with the complete gene cluster restored the AA adhesion. Overall, we found the agg5A gene in 12% of the 118 strains isolated from Denmark, suggesting that this novel adhesin represents an important variant.