Icing of various surfaces is often a result of the collision of supercooled water drops with substrates. Ice formation from supercooled water drops is initiated by nucleation when the size of an ice embryo reaches a critical value. The lack of controlling the inception of heterogeneous nucleation and the rate of solidification, which depend on the properties of the substrate, temperature, and impact parameters of the liquid drop, poses a very serious challenge to the design of effective ice-preventing materials. In this exploratory experimental study, we show how a significant nucleation delay during impact of supercooled water drops can be achieved by tuning the properties of the substrate and, specifically, by introducing chemical and topographical heterogeneities on the surfaces formed by a mixture of either polymer-coated hydrophilic and hydrophobic particles or Janus particles. We have discovered that the nucleation rate during drop impact is significantly reduced on heterogeneous surfaces formed by a mixture of hydrophilic and hydrophobic particles. Exceptionally, freezing is completely prevented on surfaces made of amphiphilic Janus particles. Even after a repetition of 100 drop impact experiments, no single drop froze at all. After impact of the supercooled water drops, a rebound occurs, and afterwards smaller secondary drops are formed, which can be easily removed. Moreover, the designed surfaces demonstrate good scratch resistance and robustness. The presented findings open a promising pathway for the rational design of effective passive ice-preventing coatings using Janus particles as building blocks.