The atomic structures of two symmetric [001] tilt grain boundaries in yttria-stabilized cubic-zirconia, Sigma5 (310) and near-Sigma 13 (510), are studied by Z-contrast scanning transmission electron microscopy. Both boundaries are composed of periodic arrays of highly symmetric structural units, with a distinct unit for each boundary, Oxygen K-edge electron energy-loss spectra show that the oxygen coordination is similar between the bulk and grain boundary, indicating that oxygen ions within the grain boundary reside in distorted tetrahedral sites. Atomic models of the grain boundaries are proposed that are consistent with the experimental data. The core structures are different from previously studied metal or oxide grain boundaries and are unique to the fluorite structure, Yttrium segregation to the grain boundaries is also investigated by electron energy-loss spectroscopy. Yttrium is found to segregate preferentially to the Sigma5 grain boundary, and the spatial distribution of the segregation layer is confined to within 1 nm of the boundary plane.