The atomic-scale structure of grain boundaries (GBs) in yttria-stabilized cubic zirconia (YSZ) was investigated by high-resolution electron microscopy (HREM). Non-stoichiometric oxides have found a wide range of applications and therefore it is of importance to explore the role of GBs and their atomic-scale relaxation modes. [001] and [110] tilt GBs were examined by HREM in highly textured thin films of YSZ grown by metal-organic chemical vapor deposition (MOCVD). In addition, a special technique was developed to also allow the HREM study of twist and general GBs. GBs and triple junctions show quite dense arrangements of cation atomic columns. The GB core structures in YSZ can be contrasted to the more open structures in stoichiometric cubic oxides, such NiO, which are characterized by a relatively large GB excess volume. This appears to be due to several factors, including the necessary rearrangement of the oxygen sublattice near GBs in a CsCl2 type structure, the redeployment of oxygen vacancies near GBs, and the segregation of Y to the GB. Relative to stoichiometric oxides, such mechanisms provide additional degrees of freedom for atomic relaxations at GBs and the development of low-energy GBs. These additional relaxation modes, which result in GB cation arrangements more akin to metallic systems, are also reflected by Burgers vector dissociations observed in low-angle YSZ GBs.