While it is now evident that the two Bacteroidales species Bacteroides fragilis and Tannerella forsythia both have general O-glycosylation systems and share a common glycosylation sequon, the ability of these organisms to glycosylate a protein native to the other organism has not yet been demonstrated. Here, we report on the glycosylation of heterologous proteins between these two organisms. Using genetic tools previously developed for Bacteroides species, two B. fragilis model glycoproteins were expressed in the fastidious anaerobe T. forsythia and the attachment of the known T. forsythia O-glycan to these proteins was demonstrated by liquid chromatography electrospray ionization tandem mass spectrometry. Likewise, two predominant T. forsythia glycoproteins were expressed in B. fragilis and glycosylation with the B. fragilis O-glycan was confirmed. Purification of these proteins from B. fragilis allowed the preliminary characterization of the previously uncharacterized B. fragilis protein O-glycan. Based on mass spectrometric data, we show that the B. fragilis protein O-glycan is an oligosaccharide composed of nine sugar units. Compositional and structural similarities with the T. forsythia O-glycan suggest commonalities in their biosynthesis. These data demonstrate the feasibility of exploiting these organisms for the design of novel glycoproteins.