Using a combination of density functional theory calculations and nanomechanical testing of sputter-deposited, 110-oriented Ta _0.47C _0.34N _0.19 thin films, we show that non-metal alloying – substituting C with N atoms – in TaC results in a super-hard material with enhanced ductility. Based on the calculated elastic constants, with Pugh and Pettifor criteria for ductile character, we predict that stoichiometric and sub-stoichiometric Ta-C-N alloys are more ductile than Ta-C compounds. From nanoindentation of the as-deposited coating, we measure hardness of 43 ± 1.4 GPa. In situ scanning electron microscopy (SEM) based micro-compression of cylindrical pillars, prepared via focused ion beam milling of the coating, revealed that Ta-C-N alloys are ductile and undergo plastic deformation with a yield strength of 17 ± 1.4 GPa. The post-compression SEM images of the pillars show {111} <011¯> as the active slip system operating during compression. Additional in situ SEM based cantilever tests suggest that the Ta-C-N films exhibit superior fracture toughness compared to Ta-C coatings. Our results provide a new perspective on the role of alloying on the mechanical behavior of ultra-high temperature compounds such as transition-metal carbides.