In order to search for potentially novel plant cell wall degrading enzymes, bacterial isolates from leachate samples of a local sanitary landfill were screened. The dominant species in the xylan-degrading bacterial population was isolated and identified as Paenibacillus sp. MAEPY2. Whole genome sequencing revealed that the strain harbors multiple gene sequences encoding for xylanases from different glycosyl hydrolase families. Two of these genes, Xyn1 and Xyn4 have been cloned and expressed in Escherichia coli. A similarity analysis of the amino acid sequence of Xyn1 (22.8 kDa) resulted in identities above 90% in more than 20 identified Paenibacillus strains, possibly indicative of a major xylanase that is highly conserved in the species. In contrast, Xyn4 was 87% identity with the xylanases from Paenibacillus barcinonensis (GB: CBA13561.1), 80% identity with P. terrae HPL-003 (GB: AET58147.1), and 79% identity with P. polymyxa SC2 (GB: ADO59301.1). Both the amino acid alignment of Xyn1 and Xyn4 revealed a high degree of homology in highly conserved regions, including catalytic sites, with xylanases of glycosyl hydrolase (GH) family 11 and 10 respectively. These results imply that Xyn1 and Xyn4 facilitate xylan degradation in Paenibacillus sp. MAEPY2, and may be promising candidates for various industrial applications such as biofuel production, or bleaching in paper and pulp industry.