By selection of appropriately sized rare earth elements and suitable reaction atmosphere, a new double-perovskite-type iron oxide REBaFe2O5+w (RE = Nd and Sm) has been synthesized, with, ideally, all Fe atoms in square pyramidal coordinations when w = 0. Like in the related triple-perovskite-type YBa2Fe3O8+w, the added oxygen atoms w are accommodated in the RE layer. The homogeneity range in w is very wide, extending from 0.02(1) for RE = Sm and 0.050(6) for RE = Nd to w = 0.65 and w = 0.80, respectively, seen in O-2 at 985 degrees C without the upper homogeneity limit being crossed. The most reduced REBaFe2O5+w phases oxidize very easily, even at room temperature. The crystal structure, as seen at room temperature after quenching from ca. 1000 degrees C, is tetragonal, except for the most reduced compositions for RE = Sm (w < 0.045) and most oxidized compositions for RE = Nd (w = 0.69 as an example) which are orthorhombic. For samples with w = 0.5 low temperature (ca. 500 degrees C) annealing leads to ordering of the added oxygens within the rare earth layer. This ordering produces equal concentrations of square pyramidal and octahedral Fe3+. The ordered structure, a type which has not previously been observed, belongs to space group Pmna (no. 53) with a approximate to 4a(p), b approximate to a(p) and c approximate to 2a(p), where a(p) is the primitive cubic perovskite cell edge (a(p) approximate to 3.9 Angstrom). Structural refinements were obtained by applying the Rietveld method to synchrotron X-ray powder diffraction data.