Magnetron sputter deposition of metal/carbon nanocomposites has been explored for many metals and a few alloys. In this paper, the formation of nanocomposites based on complex high entropy alloys (HEAs) was explored, focusing on the effect of the average carbon affinity on the phase formation. Two HEA systems were compared: CoCrFeMnNi and Cr26Fe27Ni27Ta20. For each alloy, around 20-50 at% carbon was added through combinatorial co-sputtering. Thermodynamic calculations predicted decomposition of these materials into multiple alloy phases, metal carbides, and, at higher concentrations, free graphitic carbon. Free carbon was found in the coatings at carbon concentrations above 28 and 33 at% for the CoCrFeMnNi and Cr26Fe27Ni27Ta20 systems, respectively, which agreed with the theoretical predictions. However, the segregation of metallic ele-ments and the formation of crystalline carbides were suppressed by the rapid quenching during deposition. All coatings were, instead, amorphous and consisted of either a single metallic phase or a mixture of a metallic phase and sp2- and sp3-hybridized carbon. Mechanical and electrochemical tests were performed, including in-situ fragmentation tests to quantify the crack resistance. The presence of free carbon made the coatings softer than the corresponding single-phase materials. Under tensile strain, the nanocomposite coatings formed a larger number of narrower cracks and exhibited less delamination at high strains.