A new class of bulk nanocrystalline nickel dispersed with nano-scale WO3 particles has been synthesized by conventional electrodeposition to clarify the effect of the presence of nano-size dispersions on the strength and thermal stability of nanocrystalline structures. It was found that WO3 particles of an initial size of 0.1 mu m, when suspended in an electrolyte, fragmented into smaller nano-size particles, and were embedded into nanocrystalline nickel matrix of an average grain size of 45 nm during deposition. X-ray diffraction and transmission electron microscopy analyses revealed that phase transition of WO3 particles occurred from an initial monoclinic to a tetragonal structure. The cause-and-effect relation between the fragmentation and the phase transition of WO3 particles was discussed. Further hardening was confirmed in comparison with nanocrystalline pure nickel, but its increment was less than that predicted by the classical Orowan-type hardening of the particle-dislocation interaction. The discrepancy may be associated with a different dominant deformation mode which operates in a nanocrystalline regime.