Arrays of perpendicular ferromagnetic nanowires have recently attracted considerable interest for their potential use in many areas of advanced nanotechnology. We report a simple approach to create self-assembled nanowires of α-Fe through the decomposition of a suitably chosen perovskite. We illustrate the principle behind this approach using the reaction 2La0.5Sr0.5FeO3 → LaSrFeO4 + Fe + O2 that occurs during the deposition of La0.5Sr0.5FeO3 under reducing conditions. This leads to the spontaneous formation of an array of single-crystalline α-Fe nanowires embedded in LaSrFeO4 matrix, which grow perpendicular to the substrate and span the entire film thickness. The diameter and spacing of the nanowires are controlled directly by deposition temperature. The nanowires show uniaxial anisotropy normal to the film plane and magnetization close to that of bulk α-Fe. The high magnetization and sizable coercivity of the nanowires make them desirable for high-density data storage and other magnetic-device applications.