Bacterial cell growth and division require the coordinated action of enzymes that synthesize and degrade cell wall polymers. Here, we identify enzymes that cleave the d-arabinan core of arabinogalactan, an unusual component of the cell wall of Mycobacterium tuberculosis and other mycobacteria. We screened 14 human gut-derived Bacteroidetes for arabinogalactan-degrading activities and identified four families of glycoside hydrolases with activity against the d-arabinan or d-galactan components of arabinogalactan. Using one of these isolates with exo-d-galactofuranosidase activity, we generated enriched d-arabinan and used it to identify a strain of Dysgonomonas gadei as a d-arabinan degrader. This enabled the discovery of endo- and exo-acting enzymes that cleave d-arabinan, including members of the DUF2961 family (GH172) and a family of glycoside hydrolases (DUF4185/GH183) that display endo-d-arabinofuranase activity and are conserved in mycobacteria and other microbes. Mycobacterial genomes encode two conserved endo-d-arabinanases with 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.