Both in heavy-ion collisions and in magnetars very strong magnetic fields are produced, which has an influence on the phases of matter involved. In this paper we investigate the effect of strong magnetic fields (B similar to 5m(pi)(2)/e = 1.7 x 10(19) G) on the chiral symmetry restoring phase transition using the Nambu-Jona-Lasinio model. It is observed that the pattern of phase transitions depends on the relative magnitude of the magnetic field and the instanton interaction strength. We study two specific regimes in the phase diagram, high chemical potential and zero temperature and vice versa, which are of relevance for neutron stars and heavy-ion collisions, respectively. In order to shed light on the behavior of the phase transitions, we study the dependence of the minima of the effective potential on the occupation of Landau levels. We observe a near degeneracy of multiple minima with differing occupation numbers, of which some become the global minimum upon changing the magnetic field or the chemical potential. These minima differ considerably in the amount of chiral symmetry breaking and, in some cases, also of isospin breaking.