Epitaxial Fe(110) self-assembled nanostructures are fabricated on Mo(110) by pulsed laser deposition. For high deposition temperature (~450°C), the Stransky-Krastanov growth mode leads to three-dimensional Fe islands elongated along [001] with perfectly defined facets. The morphology of the islands is well reproduced by surface energy minimization calculation. The magnetic anisotropy is shown to be dominated by the island shape. The remanence is non-zero for islands dimensions smaller than 450nm, together with a coercivity of the order of 25mT. For lower deposition temperature (~250°C), kinetic diffusion limitations lead to the formation of wire-shaped islands. This results in an increase of the nanostructures coercive field in the in-plane easy-axis direction to about 70mT.