The effects of substrate preparation on the structure and orientation of MgO films grown on (001) GaAs using pulsed laser deposition has been investigated. Textured MgO films displaying a (111)MgO parallel-to (001)GaAs orientation relation with x-ray rocking curve full width at half maximum (FWHM) values as low as 1.8-degrees were obtained in cases where the native GaAs surface oxide was only partially desorbed prior to growth. Reflection high-energy electron diffraction, transmission electron microscopy (TEM), and x-ray pole figure analysis of these films reveals a preferential orientation within the plane of the substrate: [110]MgO parallel-to BAR [110]GaAs BAR and [112]MgO parallel-to BAR [110]GaAs. An interfacial layer (approximately 5 nm thick) was observed in high resolution TEM analysis, and was attributed to a remnant native GaAs oxide layer. Complete desorption of the native GaAs oxide at approximately 600-degrees-C in vacuum prior to MgO growth led to significant surface roughening due to Langmuir evaporation, and resulted in randomly oriented polycrystalline MgO films. Growth of MgO on Sb-passivated GaAs substrates, which provided smooth, reconstructed surfaces when heated to 350-degrees-C in vacuum, resulted in cube-on-cube oriented films [i.e., (001)MgO parallel-to (001)GaAs,[100]MgO parallel-to [100]GaAs] with x-ray rocking curve FWHM values as low as 0.47-degrees. TEM analysis of the cube-on-cube oriented films revealed evidence of localized strain fields at the MgO/GaAs interface, indicating the presence of misfit dislocations in the MgO layer.