Viscous relaxation rates of craters are examined to discriminate among models of Europa's interior. It is shown that the presence of an insulating surface regolith is required for ice lithospheres that do not contain a liquid H2O layer. Without the presence of such an insulating regolith, relaxation times for craters ≂100 km in diameter are excessively long (>1 b.y.) and thus inconsistent with the absence of such features in Voyager images. Finite element calculations indicate that a thick insulating surface frost layer (raising surface temperatures >40 K above the solar radiation ambient temperture of 92 K) allows a 25-km- thick surface viscous layer to relax >100-km- diameter craters on the short timescales (≂100 m.y.) required. If the icy lithosphere is 100 km thick (and without a liquid H2O layer, but containing a subsolidus convecting region), surface temperatures need to be raised 20 K by insulation to allow relaxation of craters in this size range to occur within the required time.