The GdBaCo2O5+x oxide has been presented as a promising cathode material for solid oxide fuel cells. It presents very high oxygen exchange and diffusion coefficients, two characteristics of utmost importance for an efficient cathode material. Yet the understanding at atomic scale of these two properties is rather limited. Here, we performed calculations to understand the influence of rare-earth nature in REBaCo2O5.5 (RE=Gd, La, Y) on material stability and oxygen diffusion properties. Through energy minimisation, we determined the most energetically favourable distribution of A-site cations and oxygen vacancies. We also investigated with Molecular Dynamics simulations the mechanisms of oxygen diffusion in A-site ordered REBaCo2O5.5. The results confirm that oxygen vacancies essentially lie in the RE-plane and that diffusion is mainly two-dimensional with oxygen moving in the (a,b) plane while diffusion along the c axis is strongly hindered. Between 1300 and 1900 K. the activation energy for oxygen diffusion lies in the range 0.69-0.83 eV depending on the RE cation nature, values in good agreement with the experimental ones. We show that, in the double perovskite structure, the replacement of Gd by a larger rare-earth ion enhances oxygen diffusion properties but also reduces the stability of the double perovskite structure. (C) 2011 Elsevier B.V. All rights reserved.