For an epitaxial, vicinal surface of a magnetic film, the twofold step-induced symmetry about the film normal in the atomic coordination implies a corresponding twofold magnetic surface anisotropy. We show, that for epitaxial Fe films grown on Au surfaces vicinal to the (001) plane, tilted about the in-plane (100)Au or the (110)Au axis, a strong correlation exists between the in-plane structural anisotropy in the height-height correlation function and the magnetic surface anisotropy. This correlation is clearly evident although both anisotropies are complicated functions of the vicinal angle, the tilt axis and the film thickness due to appearing reconstructions.