We study numerically the melting of a horizontal layer of a pure solid above a convecting layer of its fluid rotating about the vertical axis. In the rotating regime studied here, with Rayleigh numbers of order $10^7$, convection takes the form of columnar vortices, the number and size of which depend upon the Ekman and Prandtl numbers, as well as the geometry -- periodic or confined. As the Ekman and Rayleigh numbers vary, the number and average area of vortices vary in inverse proportion, becoming thinner and more numerous with decreasing Ekman number. The vortices transport heat to the phase boundary thereby controlling its morphology, characterized by the number and size of the voids formed in the solid, and the overall melt rate, which increases when the lower boundary is governed by a no-slip rather than a stress-free velocity boundary condition. Moreover, the number and size of voids formed are relatively insensitive to the Stefan number, here inversely proportional to the latent heat of fusion. For small values of the Stefan number, the convection in the fluid reaches a slowly evolving geostrophic state wherein columnar vortices transport nearly all the heat from the lower boundary to melt the solid at an approximately constant rate. In this quasi-steady state, we find that the Nusselt number, characterizing the heat flux, co-varies with the interfacial roughness, for all the flow parameters and Stefan numbers considered here. This confluence of processes should influence the treatment of moving boundary problems, particularly those in astrophysical and geophysical problems where rotational effects are important.