Microbial β-galactosidase enzymes are widely used as biocatalysts in industry to produce prebiotic galactooligosaccharides (GOS) from lactose. GOS mixtures are used as beneficial additives in infant formula to mimic the prebiotic effects of human milk oligosaccharides (hMOS). The structural variety in GOS mixtures is significantly lower than in hMOS. Since this structural complexity is considered as the basis for the multiple biological functions of hMOS, it is important to broaden the variety of GOS structures. In this study, residue R484 near +1 subsite of the C-terminally truncated β-galactosidase from Bacillus circulans (BgaD-D) was subjected to site saturation mutagenesis. Especially the R484S and R484H mutant enzymes displayed significantly altered enzyme specificity, leading to a new type of GOS mixture with altered structures and linkage types. The GOS mixtures produced by these mutant enzymes contained 14 structures that were not present in the wild-type enzyme GOS mixture; 10 of these are completely new structures. The GOS produced by these mutant enzymes contained a combination of (β1→3) and (β1→4) linkages, while the wild-type enzyme has a clear preference towards (β1→4) linkages. The yield of the trisaccharide β-D-Galp-(1→3)-β-D-Galp-(1→4)-D-Glcp produced by mutants R484S and R484H increased 50 times compared to that of the wild-type enzyme. These results indicate that residue R484 is crucial for the linkage specificity of BgaD-D. This is the first study showing that β-galactosidase enzyme engineering results in an altered GOS linkage specificity and product mixture. The more diverse GOS mixtures produced by these engineered enzymes may find industrial applications.