A new composite matrix was developed for a cutting tool based on tungsten carbide ligated with cobalt (WC-Co) using sintering technique. The admixtures of niobium carbide, tantalum carbide, and titanium carbide with the WC-Co matrix aim to inhibit the grain growth of WC and to promote covalent bonding at the interface. The modified WC-Co tools were coated with titanium nitride and titanium carbonitride layers by CAE-PVD technique. To substantiate the performances of the new coating-substrate systems, we have performed X-ray diffraction, atomic force microscopy, and scratch test measurements to estimate: phase content, average crystallite size, average texture coefficient, residual stress level, coating thickness, average roughness, square mean root, fractal dimension, cohesive adhesion, and adhesive adhesion. The results enable the in-depth understanding of the coating growth mechanisms and provide an objective evaluation of the coatings adhesion to the new cutting tools matrix. The results provide evidence to support the potential of TiN and TiCN coatings to enhance the working performances of the composite WC-Co cutting tools and to differentiate their properties. TiCN coating is shown to be superior to TiN coating in terms of adhesion and thus represents a better alternative for coating the modified WC-Co composite matrix.