InN thin films possessing either a novel cubic or a hexagonal phase were grown by plasma-assisted atomic layer epitaxy on an a-plane sapphire, Si(111), and GaN/sapphire templates, simultaneously. Two ALE growth temperature windows were found between 175–185 °C and 220–260 °C, in which the growth process is self-limiting. In the lower temperature ALE window, InN on an a-plane sapphire crystallized in a face-centered cubic lattice with a NaCl type structure, which has never been previously reported. InN grown on other substrates formed the more common hexagonal phase. In the higher temperature ALE window, the InN films grown on all substrates were of hexagonal phase. The NaCl phase and the epitaxial nature of the InN thin films on the a-plane sapphire grown at 183 °C are confirmed independently by X-ray diffraction, transmission electron microscopy, and numerical simulations. These results are very promising and demonstrate the tremendous potential for the PA-ALE in the growth of crystalline III-N materials with novel phases unachievable by other deposition techniques.