The structure, structure evolution and microhardness of nanocrystalline Ni-Mo-B alloys were studied by X-ray diffraction, differential scanning calorimetry, transmission and high resolution electron microscopy and microhardness measurements. The nanocrystalline structure was produced by controlled crystallization of amorphous alloys. The annealed samples consist of the FCC nanocrystals with the amorphous regions between them. The grain size of the nanocrystals is about 20 nm and depends on the chemical composition of the alloy. The chemical composition of the amorphous phase between the nanocrystals changes at the annealing. A slight grain growth was observed when the annealing time increases. The diffusion of Mo and B from FCC to the amorphous phase occurs at the annealing. It results in the lattice parameter change. The microhardness of the alloys increases during the annealing. The microhardness values are the same in all alloys before the nanocrystalline structure decomposition. The microhardness is inconsistent with the Fetch-Hall equation. The microhardness of the alloys is determined by the microhardness of the amorphous phase bands located between the nanocrystalline grains.