Atomic structure and surface stress changes are measured simultaneously by surface x-ray diffraction and by the crystal curvature technique during the deposition of Ni on W(110). Substantial lateral shifts of up to 0.5 Å of the W atoms upon deposition of the first layer Ni are detected. This unexpected restructuring of the W surface is correlated with compressive surface stress of τ₁₁₀= -1 N/m and τ₀₀₁ = -2.1 N/m. The atomic coordinates for Ni and W atoms of this c-(1x7) structure are given and they indicate the formation of chains between Ni and W atoms along W[111].