The survey of carbohydrate active enzymes in genomic data uncovered the modular architecture of most of these proteins. Many of the additional modules associated with catalytic modules tightly bind carbohydrates. The primary role of these carbohydrate-binding modules (CBMs) is to enhance the enzymatic activity of the ensemble by bringing their appended catalytic module(s) in intimate contact with their substrates. Biochemical and biophysical approaches have unraveled the subtle interplay of the modules and the structural basis for their ligand specificities, but little attention has been paid to the evolutionary mechanisms leading to the appearance of modular architecture in carbohydrate active enzymes. Focusing on the promiscuous family CBM6 modules, we investigated the evolution of substrate specificities in parallel to that of their respectively appended catalytic modules. An extensive phylogenetic analysis of family CBM6 modules indicates that these noncatalytic modules have diverged into clades which coincide with their substrate selectivity. These data as well as the remarkable congruence of the phylogenetic trees inferred from CBM6s on the one hand and their associated catalytic modules on the other hand show that CBM6s and their associated glycoside hydrolases have coevolved to acquire the same substrate specificity. We also propose an evolutionary scenario explaining the emergence of the modular agarases, by which existent alpha-agarases acquired their agar-binding CBM6 module through a lateral transfer from pre-existing beta-agarases. Altogether, this observed coevolution between CBM6s and their catalytic modules will facilitate the prediction of the substrate specificity of uncharacterized CBM6 modules present in genomic data.