Previous studies have suggested that water-soluble polysaccharides from fermented carrot pulp (WSP-p) have stronger anti-diabetic effects than those from un-fermented carrot pulp (WSP-n). This study aimed to improve understanding of these functional differences by comparing their molecular structures. Weight-average molecular weights of WSP-p fractions were lower than those of the corresponding WSP-n fractions. While both WSPs had similar functional groups, more fragmented particles were observed on the surface of large particles of WSP-n than WSP-p. Monosaccharide composition and methylation analysis confirmed that both WSP-p and WSP-n were pectic polysaccharides, containing rhamnogalacturonan-I-type polysaccharides with 1,4-linked α-d-galacturonic acid residues and homogalacturonan regions with 1,4-GalpA linkages. 1H and 13C NMR showed that they had similar linkage patterns. These findings suggested that probiotic fermentation of WSP mainly cleaved the linkages between repeating units, and resulted in less polydisperse molecular size distributions.