In this paper, we present experimental data on synthesis and investigation of the mechanical properties of bulk nickel and bulk "nickel - 8 mol.% Y2O3-92 mol.% ZrO2" nanocomposite with a nickel matrix containing crystalline ceramic nanoparticles. In terms of wt.%, this nanocomposite (hereinafter called Ni-YSZ nanocomposite) contains 1 wt.% of ceramic nanoparticles. The Ni and Ni-YSZ nanocomposite specimens were fabricated by powder metallurgy technique with successive annealing at 1250 °C. In tension and compression tests, we revealed stress-strain dependences showing degradation of strength and ductility exhibited by Ni-YSZ nanocomposite, as compared to those of pure Ni fabricated in the same conditions. The fatigue tests of the specimens were performed in the symmetric tensioncompression regime based on 107 cycles. The fatigue limits were identified. The specimen fabricated from pure Ni powder showed the fatigue limit of 110 MPa, whereas Ni-YSZ composite exhibited the fatigue limit of 50 MPa. Thus, the insertion of ceramic nanoparticles into Ni matrix gives rise to more than two times decrease of the fatigue limit, as compared to pure Ni. The fractography of fatigue fracture surfaces was examined by scanning electron microscopy. In both materials tested, three stages of the fatigue crack distribution are observed which are the crack initiation, stable crack growth and unstable crack growth stages. Both materials contain the significant amounts of pores, and pore merging is observed at the unstable crack growth stage.