The viscosity of ice I is grain size dependent for temperature and stress conditions appropriate for ice I shells and mantles of large and midsized icy satellites. Satellite thermal evolution, heat flux, critical shell thickness for convection, brittle/ductile transition temperature, and potential for surface deformation are therefore grain size dependent. Using measured grain sizes from terrestrial ice sheets experiencing temperature and strain rate conditions similar to convecting ice shells in icy satellites, we develop two end-member models of grain size and its evolution. In the absence of non--water ice impurities, grain size in a convecting ice shell of a large icy satellite will evolve over time to an equilibrium value, which we determine to be between 30 and 80 mm, because of dynamic recrystallization. Such large grains imply viscous ice, so convection in an ice shell thinner than 35 km in a large icy satellite such as Ganymede and Callisto would be sluggish at best and may cease after a few convective overturns (if it starts). Soluble ions and silicate microparticles may keep grains small, however, of order 1--5 mm, and permit convection in shells as thin as 30 km in large icy satellites. The dynamic recrystallization model provides a plausible upper limit on grain size in a geodynamically evolved ice shell, whereas grain sizes from dust-contaminated terrestrial ice cores provide a plausible lower limit on grain size in an icy satellite. On the basis of these constraints, grain sizes in evolved ice shells of large water ice satellites, in the absence of tidal forcing, should be of order 1 mm to 10 cm.