The undesirable buildup of ice can compromise the operational safety of ships in the Arctic to high-flying airplanes, thereby having a detrimental impact on modern life in cold climates. The obstinately strong adhesion between ice and most functional surfaces makes ice removal an energetically expensive and dangerous affair. Hence, over the past few decades, substantial efforts have been directed toward the development of passive ice-shedding surfaces. Conventionally, such research on ice adhesion has almost always been based on ice solidified from pure water. However, in all practical situations, freezing water has dissolved contaminants; ice adhesion studies of which have remained elusive thus far. Here, we cast light on the fundamental role played by various impurities (salt, surfactant, and solvent) commonly found in natural water bodies on the adhesion of ice on common structural materials. We elucidate how varying freezing temperature & contaminant concentration can significantly alter the resultant ice adhesion strength making it either super-slippery or fiercely adherent. The entrapment of impurities in ice changes with the rate of freezing and ensuing adhesion strength increases as the cooling temperature decreases. We discuss the possible role played by the in situ generated solute enriched liquid layer and the nanometric water-like disordered ice layer sandwiched between ice and the substrate behind these observations. Our work provides useful insights into the elementary nature of impure water-to-ice transformation and contributes to the knowledge base of various natural phenomena and rational design of a broad spectrum of anti-icing technologies for transportation, infrastructure, and energy systems.