NbO terminated Nb(110) and its oxidation are examined by scanning tunneling microscopy and spectroscopy (STS). The oxide structures are strongly influenced by the structural and electronic properties of the underlying NbO substrate. The NbO is terminated by one-dimensional few-nanometer nanocrystals, which form an ordered pattern. High-resolution STS measurements reveal that the nanocrystals and the regions between the nanocrystals exhibit different electronic characters. Low-dosage oxidation, sufficient for sub-monolayer coverage of the NbO, with subsequent UHV annealing results in the formation of resolved sub-nanometer clusters, positioned in-between the nanocrystals. Higher dosage oxidation results in the formation of a closed Nb2O5-y layer, which is confirmed by X-ray photoelectron spectroscopy measurements. The pentoxide is amorphous at the atomic-scale. However, large scale (tens of nanometers) structures are observed with their symmetry matching that of the underlying nanocrystals.