We develop a nucleation-based model to explain the formation of the wurtzite phase during the catalyzed growth of freestanding nanowires of zinc blende semiconductors. We show that in vapor-liquid-solid nanowire growth, nucleation generally occurs preferentially at the triple phase line. This entails major differences between zinc blende and wurtzite nuclei. Depending on the pertinent interface energies, wurtzite nucleation is favored at high liquid supersaturation. This explains our systematic observation of zinc blende during early growth of gold-catalyzed GaAs nanowires.