Glycoside phosphorylases (EC 2.4.x.x) carry out the reversible phosphorolysis of glucan polymers, producing the corresponding sugar 1-phosphate and a shortened glycan chain. β-1,3-Glucan phosphorylase activities have been reported in the photosynthetic euglenozoan Euglena gracilis, but the cognate protein sequences have not been identified to date. Continuing our efforts to understand the glycobiology of E. gracilis, we identified a candidate phosphorylase sequence, designated EgP1, by proteomic analysis of an enriched cellular protein lysate. We expressed recombinant EgP1 in Escherichia coli and characterized it in vitro as a β-1,3-glucan phosphorylase. BLASTP identified several hundred EgP1 orthologs, most of which were from Gram-negative bacteria and had 37–91% sequence identity to EgP1. We heterologously expressed a bacterial metagenomic sequence, Pro_7066 in E. coli and confirmed it as a β-1,3-glucan phosphorylase, albeit with kinetics parameters distinct from those of EgP1. EgP1, Pro_7066, and their orthologs are classified as a new glycoside hydrolase (GH) family, designated GH149. Comparisons between GH94, EgP1, and Pro_7066 sequences revealed conservation of key amino acids required for the phosphorylase activity, suggesting a phosphorylase mechanism that is conserved between GH94 and GH149. We found bacterial GH149 genes in gene clusters containing sugar transporter and several other GH family genes, suggesting that bacterial GH149 proteins have roles in the degradation of complex carbohydrates. The Bacteroidetes GH149 genes located to previously identified polysaccharide utilization loci, implicated in the degradation of complex carbohydrates. In summary, we have identified a eukaryotic and a bacterial β-1,3-glucan phosphorylase and uncovered a new family of phosphorylases that we name GH149.