First-principles calculations and molecular-dynamics simulations are employed in this study to further our understanding of the crystal structure and orientational order of carbonate ions in vaterite, which is the least stable polymorph of calcium carbonate. The structural details of vaterite have been controversial but they are prerequisite for investigating and understanding the processes involving vaterite crystal nucleation, growth, and stabilization at a molecular level. The first-principles calculations, using density functional theory with the plane-wave pseudopotential method, are carried out to calculate relative thermodynamic stabilities of proposed structures. Molecular-dynamics simulations with classical empirical potentials, larger computational cells, and fully flexible models at different temperatures are performed to investigate the orientation and order-disorder of the carbonate ions. The results show that the previously accepted structure with disordered CO3 ions, which are randomly distributed over three orientations parallel to the c axis, is only metastable. By applying a temperature annealing technique to the molecular dynamics simulations, a more stable structure with fully ordered carbonate ions is found that has a hexagonal superstructure. The space group of this newly derived vaterite structure is P6522 (no. 179) with Z = 18 and cell dimensions of √3 times in a, and 3 times in c of the previous suggested disordered structure. Comparison of experimental observations of X-ray diffraction patterns, enthalpies of transformation to calcite, and volume change by heat treatment with our theoretical calculations indicates that freshly made vaterite is often carbonate-disordered and metastable and can fully or partially transform to a carbonate-ordered structure by aging and heating.