Traditional sorting diagrams for ground states (T = 0 stable atomic configurations) of bcc-based binary alloys predict simple crystal structures when simple parametric interactions (e.g., first few pairs) are assumed. However, the range and magnitude of interactions for real systems is not a priori known, and could lead to much greater structural complexity. We combine a density functional theory based, deterministic mixed-basis cluster expansion with an exhaustive enumeration scheme of 3 × 106 possible structures to determine the ground states of the bcc alloy Mo-Ta. The result is a rich ground-state line, changing one’s outlook on bcc structural stability. We find Mo-rich (100) superlattices (including C11b and B2) coexisting with complex large-cell structures (Mo4Ta9 and Mo4Ta12). We demonstrate that a systematic cluster expansion construction scheme which includes both high-order pairs and many-body figures is a necessity to capture the ground states of Mo-Ta. © 2004 The American Physical Society.