Nucleation mechanisms occurring during dynamic recrystallization play a crucial role in the evolution of microstructures and textures during high temperature deformation. In polycrystalline ice, the strong viscoplastic anisotropy induces high strain heterogeneities between grains which control the recrystallization mechanisms. Here, we study the nucleation mechanisms occurring during creep tests performed on polycrystalline columnar ice at high temperature and stress ( T =−5°C; σ =0.5 MPa) by post-mortem analyses of deformation microstructures using cryogenic electron backscatter diffraction. The columnar geometry of the samples enables discrimination of the nuclei from the initial grains. Various nucleation mechanisms are deduced from the analysis of the nuclei relations with the dislocation sub-structures within grains and at grain boundaries. Tilt sub-grain boundaries and kink bands are the main structures responsible for development of polygonization and mosaic sub-structures. Nucleation by bulging at serrated grain boundaries is also an efficient nucleation mechanism near the grain boundaries where strain incompatibilities are high. Observation of nuclei with orientations not related to the ‘parent’ ones suggests the possibility of ‘spontaneous’ nucleation driven by the relaxation of the dislocation-related internal stress field. The complexity of the nucleation mechanisms observed here emphasizes the impact of stress and strain heterogeneities on dynamic recrystallization mechanisms. This article is part of the themed issue ‘Microdynamics of ice’.