We study the behavior of strongly interacting matter under a uniform intense external magnetic field in the context of nonlocal extensions of the Polyakov-Nambu-Jona-Lasinio model. A detailed description of the formalism is presented, considering the cases of zero and finite temperature. In particular, we analyze the effect of the magnetic field on the chiral restoration and deconfinement transitions, which are found to occur at approximately the same critical temperatures. Our results show that these models offer a natural framework to account for the phenomenon of inverse magnetic catalysis found in lattice QCD calculations.