Nanostructured single-phase hafnium-zirconium carbonitride powders were synthesized using a simple and fast mechanochemical synthesis approach. The critical milling duration, after which a (Hf,Zr)(C,N) solid solution formation inside a jar occurred via mechanically induced self-sustained reaction (MSR), was 10 min. After 30 min of treatment, a solid-gas reaction was completed, and as a result, a homogeneous (Hf,Zr)(C,N) powder consisting of 10–500 nm submicron particles was obtained. The phase and structure evolution of the powders after different treatment durations allowed for the establishment of possible reaction mechanisms, which included the formation of Hf/Zr/C-layered composite particles, their interaction via MSR, and further grinding and nitridization. Spark plasma sintering (SPS) was used to produce bulk hafnium-zirconium carbonitride ceramics from nanostructured powder. The sample had higher values of relative density, hardness, and fracture toughness than those for binary compounds of a similar composition.