We show that perchlorate hydrates, which have been detected at high circumpolar martian latitudes, have a dramatic effect upon the rheological behavior of polycrystalline water ice under conditions applicable to the North Polar Layered Deposits (NPLD). We conducted subsolidus creep tests on mixtures of ice and magnesium perchlorate hydrate, Mg(ClO4)2·6H2O (MP6), of 0.02, 0.05, 0.10, and 0.47 volume fraction MP6. We found these mixtures to be increasingly weak with increasing MP6 content. For mixtures with ⩽0.10 volume fraction MP6, we resolved a stress exponent of n ≈ 2 at low stresses transitioning to n ≈ 4 above 10 MPa. Scanning electron microscopy of deformed specimens revealed MP6 to be distributed as an interconnected film between ice grains. These results suggest that grain boundary sliding (GBS) may be enhanced with respect to pure ice. As the enhancement of GBS is expected in polycrystalline aggregates containing a few percent melt or otherwise weak material distributed along grain boundaries, the observed n ≈ 2 is consistent with the mutual accommodation of basal slip and GBS. If ice containing trace concentrations of MP6 is also much weaker than pure ice at low stresses, flow in the NPLD could be significantly enhanced, particularly at the warmer basal temperatures associated with higher martian obliquities.