Division and degradation of bacterial cell walls requires coordinated action of a myriad of enzymes. This particularly applies to the elaborate cell walls of acid-fast organisms such as Mycobacterium tuberculosis, which consist of a multi-layered cell wall that contains an unusual glycan called arabinogalactan. Enzymes that cleave the D-arabinan core of this structure have not previously been identified in any organism. We have interrogated the diverse carbohydrate degrading enzymes expressed by the human gut microbiota and uncovered four families of glycoside hydrolases with activity against the D-arabinan or D-galactan components of arabinogalactan. Using novel exo-D-galactofuranosidases from gut bacteria we generated enriched D-arabinan and used it to identify Dysgonomonas gadei as a D-arabinan degrader. This enabled the discovery of endo- and exo- acting enzymes that cleave D-arabinan. We have identified new members of the DUF2961 family (GH172), and a novel family of glycoside hydrolases (DUF4185) that display endo-ᴅ-arabinofuranase activity. The DUF4185 enzymes are conserved in mycobacteria and found in many microbes, suggesting that the ability to cleave these mycobacterial glycans plays an important role in the biology of diverse organisms. All mycobacteria encode two conserved endo-D-arabinanases that display different preferences for the D-arabinan-containing cell wall components arabinogalactan and lipoarabinomannan, suggesting they are important for cell wall modification and/or degradation. The discovery of these enzymes will support future studies into the structure and function of the mycobacterial cell wall.