Two new perovskite compounds, NaLaInNbO6 and NaLaInTaO6, have been synthesized. Both compounds have a rock-salt ordering of the In/Nb or In/Ta cations and a layered ordering of the Na/La. They are unusual among this family of doubly cation ordered perovskites for having a +3/+5 combination of B/B' oxidation states instead of a divalent cation and W6+. Synchrotron powder diffraction and electron diffraction data show both compounds have tetragonal root 2a(p) X root 2a(p) x 2a(p) unit cells. The octahedral tilt system of these compounds is complicated and seems to vary depending on the length scale considered. Bond valence considerations demonstrate that none of the tilt systems compatible with a tetragonal unit cell produce a stable structure. It is proposed that additional oxygen displacements are occurring on a local scale. The XRD data show that the B -site ordering is nearly complete in both cases, while the A-site cations show a lower degree of order. The tendency of the B'-cation to undergo a second order Jahn-Teller distortion is identified as having an influence over the degree of A -site ordering. Transmission electron microscopy shows fragmentation into nanosized domains with perpendicular orientations of the layered A-site cation ordering. Such structures may be polar over short length scales which could lead to interesting dielectric properties such as relaxor behavior. The prospects for finding new doubly cation ordered perovskites are also discussed.