Physicochemical characteristics of whey protein concentrate (WPC35, 35% protein), whey protein isolate, sodium, and calcium caseinate powders were studied by storing them at 25, 35, and 45 °C and 11, 44, and 85% relative humidity (RH) for 21 days. Monolayer moisture content (Mo) in these powders increased with increasing protein content. The glass transition temperature (Tg) of all of these powders decreased with increasing RH at all storage temperatures. Lactose crystallization occurred in WPC35 at 85% RH at all temperatures and 44% RH and 45 °C, and this caused caking. Caking was also observed in whey protein concentrate and isolate, and sodium and calcium caseinate powders at 85% RH and 45 °C, despite having low (0.2–1.5%, w/w) lactose content. Surface fat content was higher in powders stored at higher temperatures and RH. All powders developed browning, which was especially pronounced at 85% RH. These findings help better understand the temperature and humidity dependent behavior of whey protein and casein powders during storage.