The structural and magnetic properties of Fe-Pd nanostructures grown on regular alternating Pd and oxygen stripes on the W(110) surface are studied using SPELEEM methods. The self-organized Pd-O stripe template, formed at about 1000°C and aligned with the [001] direction, has an average period of only few tens nm and is preserved upon quenching the sample temperature to ambient conditions. Fe is shown to preferentially bond to the Pd stripes, forming an Fe-Pd surface alloy within the stripe phase. The magnetic easy axis is found to be aligned perpendicular to the Fe-Pd stripe axis.