Elemental barium adopts a series of high-pressure phases with such complex crystal structures that some of them have eluded structure determination for many years. Using single-crystal synchrotron X-ray diffraction and new data analysis strategies, we have now solved the most complex of these crystal structures, that of phase Ba-IVc at 19 GPa. It is a commensurate host-guest structure with 768 atoms in the representative unit, where the relative alignment of the guest-atom chains can be represented as a two-dimensional pattern with interlocking S-shaped 12-chain motifs repeating regularly in one direction and repeating with constrained disorder in the other. The existence of such patterning on the nanometre scale points at medium-range interactions that are not fully screened by the itinerant electrons in this metal. On the basis of first-principles electronic structure calculations, pseudopotential theory and an analysis of the lattice periodicities and interatomic distances, we rationalize why the Ba phases with the common densely packed crystal structures become energetically unfavourable in comparison with the complex-structured Ba-IVc phase, and what the role of the well-known pressure-induced s-d electronic transfer is.