The initial stages of oxygen adsorption on Ni3Al(110) at 9700 K have been studied by scanning tunneling microscopy (STM) and low energy electron diffraction (LEED). We report the observation of two different reconstructed surface phases. First, on the well-ordered surface, after exposure to O-2 at 970 K for doses < 5L, a saturation coverage (1/4 ML) of Ni3Al{110} c(2 x 2)-O is observed. Secondly, we report an oxygen-induced reconstruction which is incommensurate with the substrate, resulting after an incomplete annealing of the suface following Ar+ bombardment. A structure model for this phase is proposed.