Progress in the development of rechargeable Ca-ion batteries demands the discovery of potential cathode materials. Transition metal oxides are interesting candidates due to their theoretical high energy densities, but with the drawback of a low Ca mobility. Previous computational/experimental investigations associate the electrochemical inactivity of various oxides (CaMO3-perovskite, CaMn2O4-post-spinel and CaV2O5) to high energy barriers for Ca migration. The introduction of oxygen and/or Ca vacancies in ternary transition metal oxides is a likely way to reshape the local topology and hence improve the Ca diffusivity. In this work, the energy barriers for Ca migration are calculated and discussed for (i) oxygen-deficient perovskites within the related Ca2Fe2O5-brownmillerite and Ca2Mn2O5 structures, and (ii) tunnel CaMn4O8, a derivative of the CaMn2O4-marokite with Ca vacancies.