The overlayer covering a (110) face of a Nb crystal annealed at 1500--2000 K in UHV has been studied by Auger electron and photoemission spectroscopies, low-energy electron diffraction (LEED) and scanning tunneling microscopy (STM). This layer, which results from the surface segregation of oxygen dissolved in Nb bulk, corresponds to a thin niobium oxide with a ${\mathrm{NbO}}_{x\ensuremath{\approx}1}$ stoichiometry as shown by photoemission with synchrotron radiation. Both LEED and STM investigations show the complex structure of the oxide overlayer with two orientations rotated by 109\ifmmode^\circ\else\textdegree\fi{}. LEED diagrams reveal the epitaxial relationship between lattices of the oxide overlayer and the metal. From STM observations, each domain in the oxide layer consists of a quasiperiodic arrangement of strictly parallel sticks. Analysis of all the results shows that each stick characterizes a small NbO crystal with a typical $3.5\ifmmode\times\else\texttimes\fi{}1.4{\mathrm{nm}}^{2}$ size. Therefore, the oxide layer can be described as a side to side arrangement of these NbO nanocrystals (fcc) on Nb(110) (bcc). Two kinds of epitaxial relationship between these two lattices are found: (i) the relative arrangement of NbO nanocrystals is determined by the underlying Nb(110) lattice; (ii) each nanocrystal develops an epitaxy relationship with the metal surface since the NbO lattice presents one (111) plane parallel to Nb(110) and one NbO 〈110〉 direction is parallel to one Nb 〈111〉 direction (Kurdjumov-Sachs-type alignment). The origin of this structure is discussed in terms of NbO/Nb misfit.