We report evidence of deformation at sub-freezing temperatures beneath Hagafellsjökull-Eystri, an Icelandic surge-type glacier. The bed of a piedmont lobe that advanced during the 1999 surge comprises deformed blocks of glacier ice set within frozen sediment. This material has also been injected through overlying ice to form a network of crevasse-squeeze ridges. This layer contains evidence for two phases of deformation under contrasting theological conditions: (1) deformation under relatively warm conditions, when the blocks of glacier ice acted as competent clasts within an unfrozen deforming matrix and (2) subsequent deformation at sub-freezing temperatures when the ice blocks were attenuated into the surrounding frozen matrix along fractures and planar shears enriched with excess ice. This suggests that the basal thermal regime of the advancing ice margin changed from warm-based to cold-based during the surge event. The persistence and potential prevalence of subglacial sediment deformation at sub-freezing temperatures has fundamental implications for our understanding of the dynamic behaviour, sediment flux and geomorphic ability of cold-based glaciers.