Icephobic surfaces have a critical footprint on human daily lives ranging from aviation systems and infrastructures to energy systems, but creation of these surfaces for low-temperature applications remains elusive. Non-wetting, liquid-infused and hydrated surfaces have inspired routes for development of icephobic surfaces. However, high freezing temperature, high ice adhesion strength and subsequent ice accretion, low mechanical durability, and high production cost have restricted their practical applications. In this review, we provide a comprehensive definition for icephobicity through thermodynamics, heat transfer and mechanics of ice/water-material interface and elucidate physic-based routes through which nano-scale could help to achieve exceptional icephobic surfaces. Based on conservation laws, mathematical models are developed that accurately predict ice growth rate on various substrates and wind conditions. Through physics of fracture at ice-icephobic material interface, we cast a standard method for ice adhesion measurement that has the potential to eliminate discrepancies between reported ice adhesion from different laboratories. To assure long-time performance of icephobic surfaces, durability metrics need to be defined. We provide standard methods to examine mechanical, chemical, and environmental durability of icephobic surfaces. In the developed comprehensive framework on icephobicity in this review, performance of state-of-the-art icephobic surfaces are compared and main deficiencies in this field are highlighted.