Complex craters with diameters (D) ≥ 40 km on Callisto and Ganymede are shallower than would be expected from simply extrapolating the depth-diameter trend from smaller (D ≤ 40 km) craters. This unusual depth-diameter (d-D) trend, and associated changes in crater morphology, have been hypothesized to result from rheological transitions, including the existence of an ocean, within the moons' ice shell. Simulations of impact crater formation can reproduce the observed shallow depths but require heat fluxes roughly twice the maximum radiogenic flux to do so. Here we demonstrate that the d-D trends on Callisto and Ganymede can instead be explained as a direct consequence of viscous relaxation under radiogenic heating. We use numerical simulations of viscous relaxation to show that if craters form at the depth expected from an extrapolation of the complex crater d-D trend, they will evolve to the observed depths over timescales of 200 Myrs to 1 Gyrs. Large craters (e.g., D ≥ 80 km) younger than 200 Myrs, which would retain greater depths, should be relatively rare. If we instead assume that the craters formed at their observed depths, as proposed by previous impact modeling, they quickly become much shallower than observed. We find excellent agreement between observed crater depths on Ganymede and our simulated crater depths by assuming a pure-water ice composition and a diurnally averaged surface temperature of 120 K, but require either larger-grained or “dirty” ice with a modestly higher viscosity to match observations at Callisto, where the surface temperature is warmer (130 K). We favor the latter explanation because it is consistent with the existence of a dusty lag on Callisto's surface and the absence of a similar lag on Ganymede. Our results predict that, for a given crater diameter, post-relaxation crater depth should increase with increasing latitude, a hypothesis best tested on Callisto, whose relatively quiescent geologic history best preserves the signature of viscous relaxation under radiogenic heating.