Spontaneous removal of liquid, solidifying liquid and solid forms of matter from surfaces, is of significant importance in nature and technology, where it finds applications ranging from self-cleaning to icephobicity and to condensation systems. However, it is a great challenge to understand fundamentally the complex interaction of rapidly solidifying, typically supercooled, droplets with surfaces, and to harvest benefit from it for the design of intrinsically icephobic materials. Here we report and explain an ice removal mechanism that manifests itself simultaneously with freezing, driving gradual self-dislodging of droplets cooled via evaporation and sublimation (low environmental pressure) or convection (atmospheric pressure) from substrates. The key to successful self-dislodging is that the freezing at the droplet free surface and the droplet contact area with the substrate do not occur simultaneously: The frozen phase boundary moves inward from the droplet free surface toward the droplet-substrate interface, which remains liquid throughout most of the process and freezes last. We observe experimentally, and validate theoretically, that the inward motion of the phase boundary near the substrate drives a gradual reduction in droplet-substrate contact. Concurrently, the droplet lifts from the substrate due to its incompressibility, density differences, and the asymmetric freezing dynamics with inward solidification causing not fully frozen mass to be displaced toward the unsolidified droplet-substrate interface. Depending on surface topography and wetting conditions, we find that this can lead to full dislodging of the ice droplet from a variety of engineered substrates, rendering the latter ice-free.