A new concept of refractory high-entropy metal-ceramic composites (HEMCC) has been proposed that combines the outstanding physical properties of both high-entropy alloy (HEA) and high-entropy ceramic (HEC). As the first HEMCC system, to the best of our knowledge, TiTaNbZr-(TiTaNbZr)C, has been developed by a powder metallurgy process. The HEA and HEC phases exhibit body-centered cubic (BCC) and rock-salt B1 crystal structures, respectively, and both phases have non-equimolar chemical compositions. With the increase of the HEC phase in HEMCC, the hardness is enhanced while the density and fracture toughness are decreased. HEA50C sintered from 50 vol% HEA and 50 vol% HEC precursor powders shows a favorable combination of flexural strength (541 ± 48 MPa) and fracture toughness (6.93 ± 0.27 MPa·m1/2) at room temperature and a high compressive strength at 1300 °C (275 MPa). The optimized mechanical performance of HEMCC might be attributed to the combination of the ductile HEA and strong HEC phases, smaller grain size, and crack arrest at HEC/HEA interfaces.