Iron-gallium alloys Fe1-xGax exhibit an exceptional increase in magnetostriction with gallium content. We present small-angle neutron scattering investigations on a Fe0.81Ga0.19 single crystal. We uncover heterogeneities with an average spacing of 15 nm and with magnetizations distinct from the matrix. The moments in and around the heterogeneities are observed to reorient with an applied magnetic field or mechanical strain. We discuss the possible roles played by nanoscale magnetic heterogeneities in the mechanism for magnetostriction in this material.