CoCrMo-C coatings have been deposited on CoCrMo ISO 5832-12 alloy substrates by reactive magnetron sputtering from targets of the same alloy in the C2H2/Ar atmosphere. Their structure evolution with increasing carbon content as well as chemical and phase composition were investigated by X-ray diffraction, X-ray photoelectron spectroscopy and transmission electron microscopy. Hardness, Young’s modulus, and tribological properties in ambient air were studied. Results show that microstructure of deposits evolves from biphasic, containing γ (fcc) and ε (hcp) metallic phases for low carbon content, through nanocrystalline and amorphous for carbon content between 10 and 20 at.%, to quasi-amorphous nanostructural for even higher content of carbon. Segregation of amorphous carbon leads to the formation of self-organized tubular nanostructure for coatings containing more than 30 at.% of carbon. Introduction of carbon into CoCrMo alloy results in a significant increase of hardness up to 14 GPa and improvement of load-bearing capacity which reached 120 MPa. Compared to uncoated CoCrMo substrate, deposited coatings with high carbon content exhibited superior tribological properties with low friction coefficient around 0.2 and wear rate about 2 × 10−15 m3/N/m.