Freezing of atmospheric water on bituminous construction and road surfaces is a recurring event during winter. However, droplet freezing on bitumen and passive inhibition methods are poorly understood. Here we investigate relative humidity and substrate cooling effects on condensation freezing on subzero temperature bituminous surfaces and find that droplet freezing is explosive, with rapid local heating. We explain the related physics and find that relative humidity and cooling rate can affect droplet sizes and freezing temperatures. We then rationally embed phase change material microcapsules in bitumen, harnessing their latent heat to significantly delay freezing, demonstrating a viable option for frost mitigation.