B-site-layer-ordered double perovskite Ca2FeMnO6 with unusually high valence Fe4+ was found to exhibit unusual oxygen-release behaviors, contrasting with those of the B-site-disordered perovskite having the identical chemical composition. During heating, the B-site-layer-ordered compound shows a stepwise oxygen release with successive valence changes from Fe4+ to Fe3+ through an intermediate Fe3.5+, whereas the B-site-disordered compound releases oxygen in a single step. The oxygen in Ca2FeMnO6 is released only from the two-dimensional Fe layers, and this selective oxygen release stabilizes the intermediate Fe3.5+ phase with in-plane-oxygen-vacancy ordering. Therefore, the B-site order/disorder strongly affects the oxygen-release behaviors associated with the oxygen-vacancy ordering.