It is surprisingly difficult to freeze water. Almost all ice that forms under "mild" conditions (temperatures > -40 degrees C) requires the presence of a nucleating agent--a solid particle that facilitates the freezing process--such as clay mineral dust, soot or bacteria. In a computer simulation, the presence of such ice nucleating agents does not necessarily alleviate the difficulties associated with forming ice on accessible timescales. Nevertheless, in this work we present results from molecular dynamics simulations in which we systematically compare homogeneous and heterogeneous ice nucleation, using the atmospherically important clay mineral kaolinite as our model ice nucleating agent. From our simulations, we do indeed find that kaolinite is an excellent ice nucleating agent but that contrary to conventional thought, non-basal faces of ice can nucleate at the basal face of kaolinite. We see that in the liquid phase, the kaolinite surface has a drastic effect on the density profile of water, with water forming a dense, tightly bound first contact layer. Monitoring the time evolution of the water density reveals that changes away from the interface may play an important role in the nucleation mechanism. The findings from this work suggest that heterogeneous ice nucleating agents may not only enhance the ice nucleation rate, but also alter the macroscopic structure of the ice crystals that form.