Epitaxial transparent oxide NixMg1-xO (0 ≤ x ≤ 1) thin films were grown on MgO(100) substrates by pulsed laser deposition. High-resolution synchrotron X-ray diffraction and high-resolution transmission electron microscopy analysis indicate that the thin films are compositionally and structurally homogeneous, forming a completely miscible solid solution. Nevertheless, the composition dependence of the NixMg1-xO optical band gap shows a strong non-parabolic bowing with a discontinuity at dilute NiO concentrations of x < 0.037. Density functional calculations of the NixMg1-xO band structure and the density of states demonstrate that deep Ni 3d levels are introduced into the MgO band gap, which significantly reduce the fundamental gap as confirmed by optical absorption spectra. These states broaden into a Ni 3d-derived conduction band for x > 0.074 and account for the anomalously large band gap narrowing in the NixMg1-xO solid solution system.