Yttria stabilized tetragonal zirconia polycrystal (Y-TZP)/0-100 vol% molybdenum (Mo) composites were fabricated by hot-pressing a mixture of Y-TZP powder containing 3 mol% yttria and a fine Mo powder in vacuum. This composite system possessed a novel microstructural feature composed of a mutual intragranular nanostructure, in which either nanometer sized Mo particles or equivalent sized zirconia particles were located within the zirconia grains or Mo grains, respectively. Both fracture strength and toughness increased with increasing Mo content. They achieved a simultaneous improvement in strength and toughness that overcame the strength-toughness tradeoff relation. A maximum fracture strength of 2100 MPa was obtained at 70 vol% Mo content. Moreover, a fracture toughness increased dramatically with increasing Mo content above 40 vol% and exhibited 18.0 MPa·m1/2 at above 50 vol% Mo content. The relation between microstructure and mechanical properties will be discussed.