Materials for high-temperature environments are actively being investigated for deployment in aerospace and nuclear applications. This study uses computational approaches to unravel the crystallography, and thermodynamics of a promising class of refractory alloys containing aluminum. Accurate first-principles calculations, cluster expansion models, and statistical mechanics techniques are employed to rigorously analyze precipitation in a prototypical senary Al-Nb-Ta-Ti-V-Zr alloy. Finite-temperature calculations reveal a strong tendency for aluminum to segregate to a single sublattice at elevated temperatures. Precipitate and matrix compositions computed with our ab-initio model are in excellent agreement with previous experimental measurements (Soni et al., 2020). Surprisingly, conventional B2-like orderings are found to be both thermodynamically and mechanically unstable in this alloy system. Complex anti-site defects are essential to forming a stable ordered precipitate. Our calculations reveal that the instability of B2 compounds can be related to a simple electron counting rule across all binary alloys formed by elements in groups 4,5, and 6. The results of this study provide viable routes toward designing high-temperature materials for deployment in extreme environments.