Transformation of cellulose into monosaccharides can be achieved by hydrolysis of the cellulose chains, carried out by a special group of enzymes known as cellulases. The enzymatic mechanism of cellulases is well described, but the role of non-enzymatic components of the cellulose-degradation machinery is still poorly understood, and difficult to measure using experiments alone. In this study, we use a comprehensive set of atomistic molecular dynamics simulations to probe the molecular details of binding of the family-3a carbohydrate-binding module (CBM3a) and the bacterial expansin protein (EXLX1) to a range of cellulose substrates. Our results suggest that CBM3a behaves in a similar way on both crystalline and amorphous cellulose, whereas binding of the dual-domain expansin protein depends on the substrate crystallinity, and we relate our computed binding modes to the experimentally measured features of CBM and expansin action on cellulose.