Azasugars are known as potent inhibitors of glycoside hydrolases. In this study, we examined the inhibition of Cellvibrio gilvus cellobiose phosphorylase (CBP) by four azasugars (isofagomine, 1-deoxynojirimycin, castanospermine and calystegine B₂) and a non-azasugar (glucono-1,5-lactone). Isofagomine strongly inhibited CBP, whereas 1-deoxynojirimycin, castanospermine, and glucono-1,5-lactone exhibited moderate or weak inhibition. Calystegine B₂ did not inhibit CBP. Kinetic analysis in the presence of sulfate indicated that it is an extremely weak competitive inhibitor against phosphate. Moreover, crystal structures of CBP complexed with isofagomine or 1-deoxynojirimycin were determined, revealing molecular recognition of the glucosidase inhibitors by the phosphorolytic enzyme. These inhibitors are bound at subsite −1 and form several hydrogen bonds with the protein and anion (phosphate or sulfate). The strong inhibition by isofagomine is probably due to an electrostatic interaction between its endocyclic amino group and phosphate.