A series of quaternary and quinary Zintl phase thermoelectric (TE) compounds, Ca5-xYbxAl2-yInySb6 (3.07(1) ≤ x ≤ 4.88(2); 0.16(2) ≤ y ≤ 2.00), containing Al/In mixed sites as well as Ca/Yb mixed sites has been successfully synthesized by a direct arc-melting method, and the X-ray diffraction analyses indicated that the products initially adopted an orthorhombic Ba5Al2Bi6-type structure (space group Pbam, Z = 2). However, after a postannealing process at 973 K for 1 month, the particular Yb rich compounds underwent a transformation of the original structure type to a Ca5Ga2Sb6-type phase regardless of the In substitution for Al. The noticeable site preference of cationic Ca and Yb in the three available cationic sites could be understood on the basis of a size match between the central cation and the volume of the anionic polyhedra. The observed phase transition was nicely explained by DFT calculations, proving that the Ca5Ga2Sb6-type phase was energetically more favorable than the Ba5Al2Sb6-type phase for the particular Yb-rich compound. Moreover, this energy difference between the two title phases was originally the result of both the site energy in the Ca site and the bond energies in the [(Al/In)2Sb8] anionic building blocks. A series of thermoelectric property data indicated that a two-step process involving a partial/full In substitution for Al and a phase transition from the Ba5Al2Sb6-type to the Ca5Ga2Sb6-type phase successfully enhanced the electrical conductivities and the Seebeck coefficients of the title compounds. This kind of combined effect eventually resulted in a ZT improvement for the quinary compound Ca1.14(2)Yb3.86Al1.68(1)In0.32Sb6 by approximately 4 times in comparison to its quaternary predecessor Ca1.55(1)Yb3.45Al2Sb6.