Amorphous carbon (a-C) deposited via magnetron sputtering usually has high residual stress, thus deposition of thick coating is difficult. In this study, aluminum was doped into a-C by co-sputtering of graphite and Al targets to drastically reduce the residual stress and enhance the toughness but at certain expense of hardness. To restore the hardness, TiC was embedded in the a-C(Al) matrix in the form of nano-sized crystals. The resultant coating is a thick nanocomposite of nanocrystalline TiC imbedded in amorphous carbon matrix doped with aluminum, or, nc-TiC/a-C(Al). Under the experimental conditions studied, the 3-μm-thick nc-TiC/a-C(Al) coating exhibited moderately high hardness (about 20 GPa) but coupled with very high toughness (55% of plasticity during indentation deformation), and very low residual stress (0.5 GPa).