The structural patterns formed by molecular self-assembly at surfaces are usually controlled by the relative strengths of the intermolecular and molecule-substrate interactions. An additional steering neffect is present when the substrate can easily reconstruct upon molecular adsorption, which therefore drives a self-templating effect on the metal support. This is here demonstrated for the model case of Fe-Phthalocyanine molecules adsorbed on the Au(110) surface. Scanning Tunneling Microscopy shows that molecular adsorption promotes a local (1×5) surface reconstruction, which drives the assembly of molecular chains along the [1 ̄10] direction. The order and periodicity of the molecular assemblies are determined with Low Energy Electron Diffraction patterns. Density Functional Theory calculations reveal the energetic origins of the molecule-driven substrate reconstruction.