We examine four candidate mechanisms that could explain the high surface temperatures of magnetars. (1) Heat flux from the liquid core heated by ambipolar diffusion. It could sustain the observed surface luminosity \mathscrLs~1035 erg s–1 if core heating offsets neutrino cooling at a temperature Tcore>6×108 K. This scenario is viable if the core magnetic field exceeds 1016 G and the heat-blanketing envelope of the magnetar has a light-element composition. However, we find that the lifetime of such a hot core should be shorter than the typical observed lifetime of magnetars. (2) Mechanical dissipation in the solid crust. This heating can be quasi-steady, powered by gradual (or frequent) crustal yielding to magnetic stresses. We show that it obeys a strong upper limit. As long as the crustal stresses are fostered by the field evolution in the core or Hall drift in the crust, mechanical heating is insufficient to sustain persistent \mathscrLs~1035 erg s–1. The surface luminosity is increased in an alternative scenario of mechanical deformations triggered by external magnetospheric flares. (3) Ohmic dissipation in the crust, in volume or current sheets. This mechanism is inefficient because of the high conductivity of the crust. Only extreme magnetic configurations with crustal fields B>1016 G varying on a 100 meter scale could provide \mathscrLs~1035 erg s–1. (4) Bombardment of the stellar surface by particles accelerated in the magnetosphere. This mechanism produces hot spots on magnetars. Observations of transient magnetars show evidence of external heating.