We report the experimental study of the temperature-dependence of the longitudinal spin relaxation time $T_1$ of single Nitrogen-Vacancy (NV) centers hosted in nanodiamonds. To determine the relaxation mechanisms at stake, measurements of the $T_1$ relaxation time are performed for a set of individual NV centers both at room and cryogenic temperatures. The results are consistant with a temperature-dependent relaxation process which is attributed to a thermally-activated magnetic noise produced by paramagnetic impurities lying on the nanodiamond surface. These results confirm the existence of surface-induced spin relaxation processes occurring in nanodiamonds, which are relevant for future developments of sensitive nanoscale NV-based quantum sensors.