Using first-principles calculations and cluster expansion, this study generates new possible stable phases of t-LLZO containing a supervalent cation, Ta, on the Zr-site as a way to enhance the conductivity of the tetragonal crystal structure. The Monte-Carlo simulation was then used to provide further insight into the behaviour of the Ta-doped phases as a function of temperature under the canonical ensemble. The cluster expansion binary ground-state diagram generated 28 new multi-component Li₅La₃Zr_2-xTa_xO₁₂ structures that are miscible. It is found that all the structures are thermodynamically stable with negative enthalpy of formation. The Monte-Carlo temperature profile shows no phase separation, and the system mixes well at ~900K. Further density functional theory calculations were performed on the most stable generated Ta-doped LLZO structures to determine the structural properties of the structures for their application as active solid-state electrolytes. It is found that the generated structures exhibit good structural stability due to the smooth decrease in calculated lattice parameters, which indicates that the smaller the difference between the dopant ionic radius and the critical dopant radius, the higher the conductivity. Therefore, the findings provide a better understanding of the phase stability of the generated Ta-doped LLZO structures, which paves the way for further analysis of the rate of lithium-ion diffusion and the mobility of the lanthanum, zirconium, tantalum, and oxygen ions in the systems at high temperatures.