Mixtures of rock debris and ice are common in high-latitude and high-altitude environments and are thought to be widespread elsewhere in our solar system. In the form of permafrost soils, glaciers, and rock glaciers, these debris-ice mixtures are often not static but slide and creep, generating many of the landforms and landscapes associated with the cryosphere. In this review, a broad range of field observations, theory, and experimental work relevant to the mechanical interactions between ice and rock debris are evaluated, with emphasis on the temperature and stress regimes common in terrestrial surface and near-surface environments. The first-order variables governing the deformation of debris-ice mixtures in these environments are debris concentration, particle size, temperature, solute concentration (salinity), and stress. A key observation from prior studies, consistent with expectations, is that debris-ice mixtures are usually more resistant to deformation at low temperatures than their pure end-member components. However, at temperatures closer to melting, the growth of unfrozen water films at ice-particle interfaces begins to reduce the strengthening effect and can even lead to profound weakening. Using existing quantitative relationships from theoretical and experimental work in permafrost engineering, ice mechanics, and glaciology combined with theory adapted from metallurgy and materials science, a simple constitutive framework is assembled that is capable of capturing most of the observed dynamics. This framework highlights the competition between the role of debris in impeding ice creep and the mitigating effects of unfrozen water at debris-ice interfaces.