Rheological experiments on fine-grained water ice II at low strain rates reveal a creep mechanism that dominates at conditions of low stress. Using cryogenic scanning electron microscopy, we observed that a change in stress exponent from 5 to 2.5 correlates strongly with a decrease in grain size from about 40 to 6 micrometers. The grain size-sensitive creep of ice II demonstrated here plausibly dominates plastic strain at the low-stress conditions in the interior of medium- to large-sized icy moons of the outer solar system.