Chemical and structural heterogeneity and the resulting interaction of coexisting phases can lead to extraordinary behaviours in oxides, as observed in piezoelectric materials at morphotropic phase boundaries and relaxor ferroelectrics. However, such phenomena are rare in metallic alloys. Here we show that, by tuning the presence of structural heterogeneity in textured Co_1−xFe_x thin films, effective magnetostriction λ_eff as large as 260 p.p.m. can be achieved at low-saturation field of ~10 mT. Assuming λ₁₀₀ is the dominant component, this number translates to an upper limit of magnetostriction of λ₁₀₀≈5λ_eff >1,000 p.p.m. Microstructural analyses of Co_1−xFe_x films indicate that maximal magnetostriction occurs at compositions near the (fcc+bcc)/bcc phase boundary and originates from precipitation of an equilibrium Co-rich fcc phase embedded in a Fe-rich bcc matrix. The results indicate that the recently proposed heterogeneous magnetostriction mechanism can be used to guide exploration of compounds with unusual magnetoelastic properties.