Unicellular protozoa that encyst individually upon starvation evolved at least eight times into organisms that instead form multicellular fruiting bodies with spores. The Dictyostelia are the largest and most complex group of such organisms. They can be subdivided into 4 major groups, with many species in groups 1-3 having additionally retained encystment. To understand fitness differences between spores and cysts, we measured long-term survival of spores and cysts under climate-mimicking conditions, investigated spore and cyst ultrastructure, and related fitness characteristics to species ecology. We found that spores and cysts survived 22 °C equally well, but that spores survived wet and dry frost better than cysts, with group 4 spores being most resilient. Spore walls consist of three layers and those of cysts of maximally two, while spores were also more compacted than cysts, with group 4 spores being the most compacted. Group 4 species were frequently isolated from arctic and alpine zones, which was rarely the case for group 1-3 species. We inferred a fossil-calibrated phylogeny of Dictyostelia, which showed that its two major branches diverged 0.52 billion years ago, following several global glaciations. Our results suggest that Dictyostelium multicellular sporulation was a likely adaptation to a cold climate.