Six fungal-type cellulose binding domains were found in the genome of the coccolithophore Emiliania huxleyi and cloned and expressed in Escherichia coli. Sequence comparison indicate high similarity to fungal cellulose binding domains, raising the question of why these domains exist in coccolithophores. The proteins were tested for binding with cellulose and chitin as ligands, which resulted in the identification of two functional carbohydrate binding modules: EHUX2 and EHUX4. Compared to benchmark fungal cellulose binding domain Cel7A-CBM1 from Trichoderma reesei, these proteins showed slightly lower binding to birch and bacterial cellulose, but were more efficient chitin binders. Finally, a set of cellulose binding domains was created based on the shuffling of one well-functioning and one non-functional domain. These were characterized in order to get more information of the binding domain’s sequence–function relationship, indicating characteristic differences between the molecular basis of cellulose versus chitin recognition. As previous reports have showed the presence of cellulose in coccoliths and here we find functional cellulose binding modules, a possible connection is discussed.