A thorough understanding of the chemistry of PuO2 is critical to the design of next-generation nuclear fuels and the long-term storage of nuclear materials. Despite over 75 years of study, the ground-state magnetic structure of PuO2 remains a matter of much debate. Experimental studies loosely indicate a diamagnetic (DM) ground-state, whereas theoretical methods have proposed either a collinear ferromagnetic (FM) or anti-ferromagnetic (AFM) ground-state, both of which would be expected to cause a distortion from the reported Fm3[combining macron]m symmetry. In this work, we have used accurate calculations based on the density functional theory (DFT) to systematically investigate the magnetic structure of PuO2 to resolve this controversy. We have explicitly considered electron-correlation, spin-orbit interaction and noncollinear magnetic contributions to identify a hereto unknown longitudinal 3k AFM ground-state that retains Fm3[combining macron]m crystal symmetry. Given the broad interest in plutonium materials and the inherent experimental difficulties of handling this compound, the results presented in this paper have considerable implications for future computational studies relating to PuO2 and related actinide structures. As the crystal structure is coupled by spin-orbit interactions to the magnetic state, it is imperative to consider relativity when creating computational models.