Water in nature predominantly freezes with the help of foreign materials through a process known as heterogeneous ice nucleation. Although this effect was exploited more than seven decades ago in Vonnegut's pioneering cloud seeding experiments, it remains unclear what makes a material a good ice former. Here, we show through a machine learning analysis of ice nucleation simulations on a database of diverse model substrates that a set of physical descriptors for heterogeneous ice nucleation can be identified. Our results reveal that, beyond Vonnegut's original connection with the lattice match to ice, three new microscopic and experimentally accessible factors help to predict the ice nucleating ability. These are: i) the local ordering induced in liquid water; ii) the density reduction of the liquid water near the surface; and iii) the corrugation of the adsorption energy landscape felt by water. With this we take a step towards a quantitative understanding of heterogeneous ice nucleation and the in silico design of materials to control ice formation.