Incorporation of therapeutic proteins in a matrix of sugar glass is known to enhance protein stability, yet protection is often lost when exposed to high relative humidity (RH). We hypothesized that especially in these conditions the use of binary glasses of a polysaccharide and disaccharide might yield advantages for protein stability. Therefore, different amounts of the polysaccharide pullulan were introduced in freeze-dried trehalose glasses. In these homogeneous blends, the presence of pullulan above 50 weight % prevented crystallization of trehalose when exposed to high RH. Storage stability testing up to 4 weeks of the model protein β-galactosidase incorporated in pullulan/trehalose blends showed superior behavior of pure trehalose at 30°C/0% RH, while pullulan/trehalose blends yielded the best stability at 30°C/56% RH. In conclusion, binary glasses of pullulan and trehalose may provide excellent stability of proteins under storage conditions that may occur in practice, namely high temperature and high RH.