The plant cell wall degrading apparatus of anaerobic bacteria includes a large multienzyme complex termed the "cellulosome." The complex assembles through the interaction of enzyme-derived dockerin modules with the multiple cohesin modules of the noncatalytic scaffolding protein. Here we report the crystal structure of the Clostridium cellulolyticum cohesin-dockerin complex in two distinct orientations. The data show that the dockerin displays structural symmetry reflected by the presence of two essentially identical cohesin binding surfaces. In one binding mode, visualized through the A16S/L17T dockerin mutant, the C-terminal helix makes extensive interactions with its cohesin partner. In the other binding mode observed through the A47S/F48T dockerin variant, the dockerin is reoriented by 180 degrees and interacts with the cohesin primarily through the N-terminal helix. Apolar interactions dominate cohesin-dockerin recognition that is centered around a hydrophobic pocket on the surface of the cohesin, formed by Leu-87 and Leu-89, which is occupied, in the two binding modes, by the dockerin residues Phe-19 and Leu-50, respectively. Despite the structural similarity between the C. cellulolyticum and Clostridium thermocellum cohesins and dockerins, there is no cross-specificity between the protein partners from the two organisms. The crystal structure of the C. cellulolyticum complex shows that organism-specific recognition between the protomers is dictated by apolar interactions primarily between only two residues, Leu-17 in the dockerin and the cohesin amino acid Ala-129. The biological significance of the plasticity in dockerin-cohesin recognition, observed here in C. cellulolyticum and reported previously in C. thermocellum, is discussed.