Xanthan-modifying enzymes are powerful tools in studying structure-function relationships of this polysaccharide. One of these modifying enzymes is xanthan lyase, which removes the terminal side chain residue of xanthan. In this paper, the cloning and sequencing of the first xanthan lyase-encoding gene is described, i.e., the xalA gene, encoding pyruvated mannose-specific xanthan lyase of Paenibacillus alginolyticus XL-1. The xalA gene encoded a 100,823-Da protein, including a 36-amino-acid signal sequence. The 96,887-Da mature enzyme could be expressed functionally in Escherichia coli. Like the native enzyme, the recombinant enzyme showed no activity on depyruvated xanthan. Compared to production by P. alginolyticus, a 30-fold increase in volumetric productivity of soluble xanthan lyase was achieved by heterologous production in E. coli. The recombinant xanthan lyase was used to produce modified xanthan, which showed a dramatic loss of the capacity to form gels with locust bean gum.