The main roadblock on the way to practical realization of magnetoelectric devices is the lack of multiferroics with strong magnetoelectric coupling. We propose an unusual route to dramatically enhance this coupling through a thermally mediated mechanism. Such a thermally mediated magnetoelectric effect is quantified by an isentropic rather than isothermal magnetoelectric response and is computed here from first principles. A robust enhancement of the magnetoelectric coupling is predicted for both naturally occurring and heterostructured materials.