We report neutron diffuse scattering measurements on highly magnetostrictive Fe1-xGax alloys (0.14 < x < 0.20) with different thermal treatments. This diffuse scattering scales with magnetostriction and exhibits asymmetric peaks at the (100) and (300) reciprocal lattice positions that are consistent with the coexistence of short-range ordered, coherent nanometer-scale precipitates embedded in a long-range ordered, body-centered cubic matrix. A large peak splitting is observed at (300) for x=0.19, which indicates that the nanoprecipitates are not cubic and have a large elastic strain. This implies a structural origin for the enhanced magnetostriction.