Myonecrotic isolates of Clostridium perfringens secrete multimodular sialidases, often termed "large sialidases", that contribute to the virulence of this bacterium. NanJ is the largest of the two secreted sialidases at 1173 amino acids and comprises 6 different modules which are, from the N-terminus, a family 32 carbohydrate binding module (CBM), a family 40 CBM, a family 33 glycoside hydrolase, a module of unknown function, a family 82 "X-module" of unknown function, and a module with amino acid similarity to fibronectin type III domains. The hydrolase activity of clostridial sialidases is quite well documented; however, the functions of their accessory domains are entirely uninvestigated. Here we describe the carbohydrate binding activity of the isolated family 32 CBM (CBM32) and the isolated family 40 CBM (CBM40). CBM32 is shown to bind galactose or N-acetylgalactosamine, while CBM40 is sialic acid specific, though both CBMs appear to bind with very low affinities. The crystal structure of CBM32 was determined at 2.25 A in complex with galactose. This revealed what appears to be a very simple galactose binding site. The crystal structure of CBM40 was determined at 2.20 A in complex with a sialic acid containing molecule that it fortuitously crystallized with, revealing the molecular details of the CBM40-sialic acid interaction. Overall, the results indicate that NanJ contains carbohydrate specific binding modules that likely function to target the enzyme to molecules or cells bearing mixed populations of glycans that terminate in either galactose/N-acetylgalactosamine or sialic acid.