Sucrose phosphorylase is a promising biocatalyst for the glycosylation of a wide variety of acceptor molecules, but its low thermostability is a serious drawback for industrial applications. In this work, the stability of the enzyme from Bifidobacterium adolescentis has been significantly improved by a combination of smart and rational mutagenesis. The former consists of substituting the most flexible residues with amino acids that occur more frequently at the corresponding positions in related sequences, while the latter is based on a careful inspection of the enzyme's crystal structure to promote electrostatic interactions. In this way, a variant enzyme could be created that contains six mutations and whose half-life at the industrially relevant temperature of 60 °C has more than doubled compared with the wild-type enzyme. An increased stability in the presence of organic co-solvents could also be observed, although these effects were most noticeable at low temperatures.