Arabinoxylan gels with different cross-linking densities, swelling ratios, and rheological properties were obtained by increasing the concentration of arabinoxylan from 4 to 6% (w/v) during oxidative gelation by laccase. The degradation of these covalently cross-linked gels by a mixture of two Bifidobacterium strains (Bifidobacterium longum and Bifidobacterium adolescentis) was investigated. The kinetics of the evolution of structural morphology of the arabinoxylan gel, the carbohydrate utilization profiles and the bacterial production of short-acid fatty acid (SCFA) were measured. Scanning electron microscopy analysis of the degraded gels showed multiple cavity structures resulting from the bacterial action. The total SCFA decreased when the degree of cross-linking increased in the gels. A slower fermentation of arabinoxylan chains was obtained for arabinoxylan gels with more dense network structures. These results suggest that the differences in the structural features and properties studied in this work affect the degradation time of the arabinoxylan gels.