Growth evolution of InN nanostructures via a chemical vapor deposition technique is reported using In2O3 as a precursor material and NH3 as reactive gas in the temperature range of 550–700 °C. Morphology of the nanostructures solely depends on the growth temperature, evolving from quantum dot sized nanoparticles to nanorods. It is found that 630 °C is the threshold temperature for nanorod growth. At 630 °C, nucleation starts with multifaceted particles having {10–12} surface planes. Subsequently, hexagonal polyhedral NRs are grown along the [0001] direction with non-polar surfaces of m-planes {10–10}. A comprehensive study is carried out to understand the evolution of nanorods as a function of growth parameters like temperature, time and gas flow rate. The change in the morphology of nanostructures is explained based on the nucleation and the growth rates during the phase formation. Raman studies of these nanostructures show that a biaxial strain is developed because of unintentional impurity doping with the increase in growth temperature.