First-principles evolutionary simulations are used to predict the stable compounds of TiC Formula omittedN Formula omitted. Our structural searching results reveal that TiC Formula omittedN Formula omitted system has a wide compositional range and several TiC Formula omittedN Formula omitted structures with new stoichiometries are found. All the predicted TiC Formula omittedN Formula omitted compounds are dynamically stable at ambient pressure. The elastic properties, hardness and fracture toughness of these TiC Formula omittedN Formula omitted compounds have been systematically investigated. New ternary compound Ti Formula omittedC Formula omittedN Formula omitted is predicted to be the hardest and has a Vickers hardness of 29 GPa and a high fracture toughness (3.38 MPa m Formula omitted). The high hardness for Ti Formula omittedC Formula omittedN Formula omitted originates from the strong interactions between Ti-3d and C-2p electrons according to the electronic structure analysis. The relationship between elastic properties and valence electron concentration (VEC) is further discussed. The results show that the hardness and shear moduli of TiC Formula omittedN Formula omitted compounds simultaneously reach their maximum when the VEC is around 8.4.