Using small-angle neutron scattering, we demonstrate that the complex magnetic domain patterns at the surface of Nd2Fe14B, revealed by quantitative Kerr and Faraday microscopy, propagate into the bulk and exhibit structural features with dimensions down to 6 nm, the domain wall thickness. The observed fractal nature of the domain structures provides an explanation for the anomalous increase in the bulk magnetization of Nd2Fe14B below the spin-reorientation transition. These measurements open up a rich playground for studies of fractal structures in highly anisotropic magnetic systems.