β-Galactosidases catalyze the hydrolysis of β(1-3) and β(1-4) galactosyl bonds in oligosaccharides as well as the inverse reaction of enzymatic condensation and transglycosylation. Here we report the crystallographic structures of Penicillium sp. β-galactosidase and its complex with galactose solved by the SIRAS quick cryo-soaking technique at 1.90 Å and 2.10 Å resolution, respectively. The amino acid sequence of this 120 kDa protein was first assigned putatively on the basis of inspection of the experimental electron density maps and then determined by nucleotide sequence analysis. Primary structure alignments reveal that Penicillium sp. β-galactosidase belongs to family 35 of glycosyl hydrolases (GHF-35). This model is the first 3D structure for a member of GHF-35. Five distinct domains which comprise the structure are assembled in a way previously unobserved for β-galactosidases. Superposition of this complex with other β-galactosidase complexes from several hydrolase families allowed the identification of residue Glu200 as the proton donor and residue Glu299 as the nucleophile involved in catalysis. Penicillium sp. β-galactosidase is a glycoprotein containing seven N-linked oligosaccharide chains and is the only structure of a glycosylated β-galactosidase described to date.