Details of the phase decomposition in NaCl-structure Ti0.33Al0.67N thin films deposited by cathodic arc evaporation are studied by atom probe tomography. We demonstrate that as-deposited films are in the earliest stage of decomposition for which electron microscopy and x-ray diffraction indicate a single-phase solid solution. Annealing at 900 degrees C further activates spinodal decomposition of the films, although pockets of unde-composed material remain after 2 h. N preferentially segregates to the AlN and TiN domains, causing the TiAlN matrix to be understoichiometric, by the energetics of N vacancies in TiAlN. The corresponding modulation in stoichiometry implies a Kirkendall effect, caused by different Al and Ti diffusivities.