We present and characterize a novel setup to apply Second Harmonic Generation (SHG) spectroscopy in total internal reflection geometry (TIR) to heterogeneous freezing research. It allows to monitor the evolution of water structuring at solid surfaces at low temperatures prior to heterogeneous ice nucleation. Apart from the possibility of investigating temperature dependence, a major novelty in our setup is the ability of measuring sheet-like samples in TIR geometry in a direct way. As a main experimental result, we find that our method can discriminate between good and poor ice nucleating surfaces. While at the sapphire basal plane, which is known to be a poor ice nucleator, no structural rearrangement of the water molecules is found prior to freezing, the basal plane surface of mica, an analogue to ice active mineral dust surfaces, exhibits a strong change in the nonlinear optical properties at temperatures well above the freezing transition. This is interpreted as a pre-activation, i.e. an increase in the local ordering of the interfacial water which is expected to facilitate the crystallization of ice at the surface. The results ... mehrare in line with recent predictions by Molecular Dynamics simulations on a similar system.