The interface and electronic structure of thin (~20-74 nm) Co3O4(110) epitaxial films grown by oxygen-assisted molecular beam epitaxy on MgAl2O4(110) single crystal substrates have been investigated by means of real and reciprocal space techniques. As-grown film surfaces are found to be relatively disordered and exhibit an oblique low energy electron diffraction (LEED) pattern associated with the O-rich CoO2 bulk termination of the (110) surface. Interface and bulk film structure are found to improve significantly with post-growth annealing at 820 K in air and display sharp rectangular LEED patterns, suggesting a surface stoichiometry of the alternative Co2O2 bulk termination of the (110) surface. Non-contact atomic force microscopy demonstrates the presence of wide terraces separated by atomic steps in the annealed films that are not present in the as-grown structures; the step height of ~ 2.7 A corresponds to two atomic layers and confirms a single termination for the annealed films, consistent with the LEED results. A model of the (1 * 1) surfaces that allows for compensation of the polar surfaces is presented.