The formation of ice affects many aspects of our everyday life as well as important technologies such as cryotherapy and cryopreservation. Foreign substances almost always aid water freezing through heterogeneous ice nucleation, but the molecular details of this process remain largely unknown. In fact, insight into the microscopic mechanism of ice formation on different substrates is difficult to obtain even if state-of-the-art experimental techniques are used. At the same time, atomistic simulations of heterogeneous ice nucleation frequently face extraordinary challenges due to the complexity of the water-substrate interaction and the long time scales that characterize nucleation events. Here, we have investigated several aspects of molecular dynamics simulations of heterogeneous ice nucleation considering as a prototypical ice nucleating material the clay mineral kaolinite, which is of relevance in atmospheric science. We show via seeded molecular dynamics simulations that ice nucleation on the hydroxylated (001) face of kaolinite proceeds exclusively via the formation of the hexagonal ice polytype. The critical nucleus size is two times smaller than that obtained for homogeneous nucleation at the same supercooling. Previous findings suggested that the flexibility of the kaolinite surface can alter the time scale for ice nucleation within molecular dynamics simulations. However, we here demonstrate that equally flexible (or non flexible) kaolinite surfaces can lead to very different outcomes in terms of ice formation, according to whether or not the surface relaxation of the clay is taken into account. We show that very small structural changes upon relaxation dramatically alter the ability of kaolinite to provide a template for the formation of a hexagonal overlayer of water molecules at the water-kaolinite interface, and that this relaxation therefore determines the nucleation ability of this mineral.