We report Raman measurements on InN islands grown on GaN by metalorganic chemical vapor deposition. The Raman frequency of the InN E2 mode is found to decrease exponentially with the island's aspect ratio, indicating a size dependent strain relaxation during the island formation. Our results suggest that most of the strain at the InN-GaN interface have been released plastically during the initial stage of island formations. After that, the residual strain of only -3.5× 10-3 is further relaxed elastically via surface islanding. The experimental data are in agreement with the strain relaxation predicted from a simplified model analysis as well as three-dimensional finite-element simulations.