Development of advanced ternary nitride coatings such as titanium aluminium nitride and titanium vanadium nitride has attracted significant industrial interest in recent years. Titanium vanadium nitride is considered one of the advanced ternary nitride coatings of great commercial potential. It is believed with the additional element, the oxidation resistance of the coatings can be greatly improved at elevated temperatures. Furthermore, the type of elements selected can produce unique coating properties that can be beneficial to machining of different materials. This paper is to report a study on the structural stability of nanostructured titanium vanadium nitride coatings in high temperature annealing. Nanostructured titanium vanadium nitride coatings were produced by reactive magnetron co-sputtering on AISI H13 tool steel substrates at 240oC. Heat treatment was applied to the coatings at temperatures up to 1000oC. It was found that an unexpected grain refinement of the coatings occurred in the heat treatment process. Grain size of the coatings was found to decrease from ~200-300 nm to ~150 nm after the heat treatments. A strong TiN/TiVN (200) component was found to exist at temperatures up to 700oC but was depleted at higher annealing temperatures. With a finer and densified grain structure, the hardness of the coatings substantially increased from ~800 HV to ~1700 HV.