Background: MPC 80 is a high-protein (80%) milk powder commonly used in the food industry as a functional ingredient and valued for its nutritional quality. However, its rehydration properties decline during storage, causing more time to be required for rehydration of the powder by the end user. It is thought that changes at the surface of the powder particles contribute to this reduced solubility during storage. Results: Surface composition and structural changes in milk protein concentrate (MPC) were observed during 90 days of storage at temperatures of 25 and 40 °C and relative humidities of 44, 66 and 84%. No significant changes to the surface composition (fat, protein and lactose) of the MPC powder samples occurred during storage; however, some changes in the microstructure of the powders were observed. Scanning electron microscopy analysis of the powder particles during dissolution showed the formation of a crust, consisting of a thin layer of fused casein micelles, on the surface of the stored powders. An increase in the hydrophobicity at the surface of the particles was evident by X-ray photoelectron spectroscopy analysis of the bonding state of the elements at or near the surface and by atomic force microscopy measurements of the adherence of particles to the surface of a material. Conclusion: The development of this 'crust' is thought to contribute to the decrease in the solubility of the powder particles during storage. The increase in the hydrophobicity at the surface and the casein micelle interactions resulting in the surface crust formation appear to contribute to the decrease in the solubility of MPC during storage.