We have characterized the structure and dynamics of the carbohydrate-modifying enzyme Paenibacillus nanensis xanthan lyase (PXL) involved in the degradation of xanthan by X-ray crystallography, small-angle X-ray scattering, and hydrogen/deuterium exchange mass spectrometry. Unlike other xanthan lyases, PXL is specific for both unmodified mannose and pyruvylated mannose, which we find is correlated with structural differences in the substrate binding groove. The structure of the full-length enzyme reveals two additional C-terminal modules, one of which belongs to a new non-catalytic carbohydrate binding module family. Ca2+ are critical for the activity and conformation of PXL, and we show that their removal by chelating agents results in localized destabilization/unfolding of particularly the C-terminal modules. We use the structure and the revealed impact of Ca2+ coordination on conformational dynamics to guide the engineering of PXL variants with increased activity and stability in a chelating environment, thus expanding the possibilities for industrial applications of PXL.