The deconstruction of the plant cell wall is an important biological process that is attracting considerable industrial interest, particularly in the bioenergy sector. Enzymes that attack the plant cell wall generally contain one or more noncatalytic carbohydrate binding modules (CBMs) that play an important targeting function. While CBMs that bind to the backbones of plant structural polysaccharides have been widely described, modules that recognize components of the vast array of decorations displayed on these polymers have been relatively unexplored. Here we show that a family 35 CBM member (CBM35), designated CtCBM35-Gal, binds to alpha-D-galactose (Gal) and, within the context of the plant cell wall, targets the alpha-1,6-Gal residues of galactomannan but not the beta-D-Gal residues in xyloglucan. The crystal structure of CtCBM35-Gal reveals a canonical beta-sandwich fold. Site-directed mutagenesis studies showed that the ligand is accommodated within the loops that connect the two beta-sheets. Although the ligand binding site of the CBM displays significant structural similarity with calcium-dependent CBM35s that target uronic acids, subtle differences in the conformation of conserved residues in the ligand binding site lead to the loss of metal binding and uronate recognition. A model is proposed in which the orientation of the pair of aromatic residues that interact with the two faces of the Gal pyranose ring plays a pivotal role in orientating the axial O4 atom of the ligand toward Asn140, which is invariant in CBM35. The ligand recognition site of exo-CBM35s (CBM35-Gal and the uronic acid binding CBM35s) appears to overlap with that of CBM35-Man, which binds to the internal regions of mannan, a beta-polymer of mannose. Using site-directed mutagenesis, we show that although there is conservation of several functional residues within the binding sites of endo- and exo-CBM35s, the endo-CBM does not utilize Asn113 (equivalent to Asn140 in CBM35-Gal) in mannan binding, despite the importance of the equivalent residue in ligand recognition across the CBM35 and CBM6 landscape. The data presented in this report are placed within a wider phylogenetic context for the CBM35 family.