We consider the response of the QCD ground state at finite baryon density to a strong magnetic field B. We point out the dominant role played by the coupling of neutral Goldstone bosons, such as pi^0, to the magnetic field via the axial triangle anomaly. We show that, in vacuum, above a value of B ~ m_pi^2/e, a metastable object appears - the pi^0 domain wall. Because of the axial anomaly, the wall carries a baryon number surface density proportional to B. As a result, for B ~ 10^{19} G a stack of parallel pi^0 domain walls is energetically more favorable than nuclear matter at the same density. Similarly, at higher densities, somewhat weaker magnetic fields of order B ~ 10^{17}-10^{18} G transform the color-superconducting ground state of QCD into new phases containing stacks of axial isoscalar (eta or eta') domain walls. We also show that a quark-matter state known as ``Goldstone current state,'' in which a gradient of a Goldstone field is spontaneously generated, is ferromagnetic due to the axial anomaly. We estimate the size of the fields created by such a state in a typical neutron star to be of order 10^{14}-10^{15} G.