Breast-fed infants generally have a bifidobacteriarich microbiota with recent studies indicating that human milk oligosaccharides (HMOs) selectively promote bifidobacterial growth. Bifidobacterium bifidum possesses a glycoside hydrolase family 20 lacto-N-biosidase for liberating lacto-N-biose I from lacto-N-tetraose, an abundant HMO unique to human milk, while Bifidobacterium longum subsp. longum has a non-classified enzyme (LnbX). Here, we determined the crystal structure of the catalytic domain of LnbX and provide evidence for creation of a novel glycoside hydrolase family, GH136. The structure, in combination with inhibition and mutation studies, provides insight into the molecular mechanism and broader substrate specificity of this enzyme. Moreover, through genetic studies, we show that lnbX is indispensable for B. longum growth on lacto-N-tetraose and is a key genetic factor for persistence in the gut of breast-fed infants. Overall, this study reveals possible evolutionary routes for the emergence of symbiosis between humans and bifidobacterial species in the infant gut.