The structure of Ba3Nb2O8 has been investigated using high resolution neutron powder diffraction. Our results show that, while the structure has some features in common with the 9R perovskite and palmierite structures, it is a new and distinct structure. It is shown to follow a (chh)(hhc)(chh) sequence with BaO3-delta packing layers and is a cation- and anion-deficient 9H perovskite polytype. Nb atoms occupy octahedral sites with vacancies between hexagonal close-packed layers. Isolated, corner sharing and face-sharing Nb-O octahedra all occur within the unit cell. The identification of purely octahedral Nb is supported by solid-state Nb-93 wideline NMR measurements. A two-component line shape was detected: a narrow featureless resonance with an isotropic chemical shift of delta(iso) -928 +/- 5 ppm consistent with regular Nb octahedra, and a much broader featureless resonance with an approximate isotropic chemical shift in the range delta(iso) similar to -944 to -937 +/- 10 ppm consistent with Nb octahedra influenced by O vacancies. These are both characteristic of 6 -fold oxo-coordinated Nb environments. The highly distorted octahedral environments in Ba3Nb2O8 make it a potential candidate for dielectric and photocatalytic applications.