Background: Molecular evolution of carbohydrate binding modules (CBM) is a new approach for the generation of glycan-specific molecular probes. To date, the possibility of performing affinity maturation on CBM has not been investigated. In this study we show that binding characteristics such as affinity can be improved for CBM generated from the CBM4-2 scaffold by using random mutagenesis in combination with phage display technology. Results: Two modified proteins with greatly improved affinity for xyloglucan, a key polysaccharide abundant in the plant kingdom crucial for providing plant support, were generated. Both improved modules differ from other existing xyloglucan probes by binding to galactose-decorated subunits of xyloglucan. The usefulness of the evolved binders was verified by staining of plant sections, where they performed better than the xyloglucan-binding module from which they had been derived. They discriminated non-fucosylated from fucosylated xyloglucan as shown by their ability to stain only the endosperm, rich in non-fucosylated xyloglucan, but not the integument rich in fucosylated xyloglucan, on tamarind seed sections. Conclusion: We conclude that affinity maturation of CBM selected from molecular libraries based on the CBM4-2 scaffold is possible and has the potential to generate new analytical tools for detection of plant carbohydrates.