Human milk oligosaccharides (HMOs) designate a unique family of bioactive lactose-based molecules present in human breast milk. Using lactose as a cheap donor, some β-galactosidases (EC 184.108.40.206) can catalyze transgalactosylation to form the human milk oligosaccharide lacto- N-neotetraose (LNnT; Gal-β(1,4)-GlcNAc-β(1,3)-Gal-β(1,4)-Glc). In order to reduce reaction times and be able to work at temperatures, which are less welcoming to microbial growth, the current study investigates the possibility of using thermostable β-galactosidases for synthesis of LNnT and N-acetyllactosamine (LacNAc; Gal-β(1,4)-GlcNAc), the latter being a core structure in HMOs. Two hyperthermostable GH 1 β-galactosidases, Ttβ-gly from Thermus thermophilus HB27 and CelB from Pyrococcus furiosus, were codon-optimized for expression in Escherichia coli along with BgaD-D, a truncated version of the GH 42 β-galactosidase from Bacillus circulans showing high transgalactosylation activity at low substrate concentrations. The three β-galactosidases were compared in the current study in terms of their transgalactosylation activity in the formation of LacNAc and LNnT. In all cases, BgaD-D was the most potent transgalactosidase, but both thermostable GH 1 β-galactosidases could catalyze formation of LNnT and LacNAc, with Ttβ-gly giving higher yields than CelB. The thermal stability of the three β-galactosidases was elucidated and the results were used to optimize the reaction efficiency in the formation of LacNAc, resulting in 5-6 times higher reaction yields and significantly shorter reaction times.