Under certain conditions, it takes a shorter time to cool a hot system than to cool the same system initiated at a lower temperature. This phenomenon — the “Mpemba effect” — was first observed in water and has recently been reported in other systems. Whereas several detail-dependent explanations were suggested for some of these observations, no common underlying mechanism is known. We present a widely applicable mechanism for a similar effect, the Markovian Mpemba effect, derive the sufficient conditions for its appearance, and demonstrate it explicitly in the anti-ferromagnet Ising model. Interestingly, the Markovian Mpemba effect can be classified as ``weak'' or ``strong'' and as ``direct'' or ``inverse''. In the Ising model we show that the ``strong'' (direct and inverse) effect exists even in the thermodynamic limit.