Mars is thought to have possessed a dynamo that ceased similar to0.5 b.y. after the formation of the planet. A possible, but ad hoc, explanation is an early episode of plate tectonics, which drove core convection by rapid cooling of the mantle. We present an alternative explanation: that the Martian core was initially hotter than the mantle after core formation, providing an initial high heat flux out of the core. A core initially 150 K hotter than the mantle can explain the early dynamo without requiring plate tectonics. Recent experimental results suggest that potassium is likely to partition into the Martian core, potentially providing an extra source of energy to power a dynamo. We find that the radioactive decay of K-40 cannot explain the inferred dynamo history without the presence of a hot core. Our results also suggest that core solidification is unlikely to have occurred, because this process would have generated a long-lived (>1 b.y.) dynamo. If, as we conclude, the core is entirely liquid, it must contain at least similar to5 wt% sulfur. An initially hot core is consistent with geochemical evidence for rapid core formation and incomplete thermal equilibration with the mantle. Thus, the early history of planetary dynamos provides constraints on the processes of accretion and differentiation.