We study the behavior of strongly interacting matter under an external constant magnetic field in the context of nonlocal chiral quark models that incorporate a coupling to the Polyakov loop. We find that at zero temperature the behavior of the quark condensates shows the expected magnetic catalysis effect, our predictions being in good quantitative agreement with lattice QCD results. On the other hand when the analysis is extended to the case of finite temperature our results show that nonlocal models naturally lead to the Inverse Magnetic Catalysis effect for both the chiral restoration and deconfinement transition temperatures.