We have investigated the effects of O on the structure and mechanical properties of NiAl intermetallics using a first-principles pseudopotential total-energy method based on the density functional theory with the generalized gradient approximation. We found that the impurity O atom can either replace Ni atom or go into the tetrahedron interstitial site depending on the surrounding environment. In both cases, O tends to form an Al2O3-like tetrahedron structure with its nearest Al or Ni atoms, leading to the formation of the stronger O-Al bond containing covalent component. We demonstrate that the presence of O will cause an increase of the brittleness and a decrease of the ductility of NiAl based on the calculated elastic constants and the empirical criterions for both substitutional and interstitial cases. Our calculations provide a way to suppress the negative effect of O by adding the alloying element with lower electronegativity than that of Al.