Here we design a novel multi-principal element carbide system (Ti,Zr,Hf,W)C with a miscibility gap using computational tools and report on the formation of a single-phase (Ti,Zr,Hf,W)C after spark plasma sintering. The (Ti,Zr,Hf,W)C shows high nanohardness (32.7 GPa) and fracture toughness (5 MPa·m1/2). Aging studies at 1350 °C for 100 h show that the single-phase carbide solid solution is quite stable even though this temperature is within the predicted miscibility gap of the system. Detailed electron microscopy characterization shows that phase separation has initiated with minor decomposition after aging by forming rock-salt (Ti,W)C- and (Zr,Hf)C-rich phases as well as hexagonal WC precipitates. We show that the (Ti,W)C- and (Zr,Hf)C-rich phases form a lamellar structure upon aging and the interlamellar spacing is considerably coarser than what has been previously found for the binary (Ti,Zr)C system. The decomposition kinetics, on the other hand, is sluggish due to the reduced driving force for phase decomposition.