We show by high pressure torsion at room temperature and transmission electron microscopy that nucleation of recrystallized α-Mg grains occurs preferentially over quasicrystalline i-phase particles at an early stage of recrystallization in a Mg-3.0Zn-0.5Y (at%) alloy. α-Mg grains nucleated on i-phase surfaces by torsional rotation N=1/2 (at 5GPa pressure), and show definite orientation relationships with the i-phase. These orientation relationships are asymmetrical variations of those reported for as-cast and extruded alloys. The nucleated grains show a planar interface with the i-phase and are often faceted as they grow into a yet unrecrystallized matrix.