The effect of different tetravalent octahedral site substitutions on the cation ordering in Ba(Mg1/3Ta2/3)O-3 perovskites were explored by investigating the phase stabilities and structures of their solid solutions with BaTiO3, BaSnO3, and BaCeO3. In the cerate system, the 1:2 ordered form of Ba(Mg1/3Ta2/3)O-3 has very limited stability and transforms to a cubic, 1:1 ordered structure with a doubled perovskite repeat between 7 and 25 mol% BaCeO3. Structure refinements of the Ba(beta＇(1/2)beta "(1/2))O-3 phases indicate that the 1:1 order can be described by a "random site" model. In this model, the beta " sites are occupied by Ta, the beta＇ sites are occupied by a random distribution of Mg, Ce, and the remaining Ta cations, and the stoichiometry of the structure can be represented by Ba[Mg2(1-x/3)Ta(1-4x/3)Ce-2x](1/2)[Ta](1/2)O-3. Although the formation of this phase in the cerate system is similar to the results reported previously for BaZrO3 substitutions, no evidence of 1:1 order was found in the BaTiO3 solid solutions, which adopt a disordered perovskite structure for >10 mol% Ti. The correlation between the size of the tetravalent cation and the formation of the-random site structure extended to the BaSnO3 system, which also showed no evidence of an extended region of stable 1:1 order.