A beta-1,3-galactosyl-N-acetylhexosamine phosphorylase (GalGlyNAcP) homolog gene was cloned from Vibrio vulnificus CMCP6. In synthetic reactions, the recombinant enzyme acted only with GlcNAc and GalNAc as acceptors in the presence of alpha-D-galactose-1-phosphate as a donor to form lacto-N-biose I (LNB) (Gal beta 1 -> 3GlcNAc) and galacto-N-biose (GNB) (Gal beta 1 -> 3GalNAc), respectively. GlcNAc was a much better acceptor than GalNAc. The enzyme also phosphorolysed LNB faster than it phosphorolysed GNB, and the k(cat)/K(m) for LNB was approximately 60 times higher than the k(cat)/K(m) for GNB. This result indicated that the enzyme was remarkably different from GalGlyNAcP from Bifidobacterium longum, which has similar activities with LNB and GNB, and GalGlyNAcP from Clostridium perfringens, which is a GNB-specific enzyme. The enzyme is the first LNB-specific enzyme that has been found and was designated lacto-N-biose I phosphorylase. The discovery of an LNB-specific GalGlyNAcP resulted in recategorization of bifidobacterial GalGlyNAcPs as galacto-N-biose/lacto-N-biose I phosphorylases.