A new approach for electrical and thermal improvement of contacts between carbon nanostructures (multi-wall carbon nanotubes - MWCNTs and multi-layer graphene - MLG) and metal electrodes by localized laser heating is presented. The nanostructures were deposited over electrodes using the dielectrophoresis (DEP) technique. A focused laser beam was used for direct heating the samples in ambient atmosphere. The Raman spectroscopy was used to determine the process temperature by observations of the graphitic C-line downshift. In the laser annealing experiments, the C-line position was found first to downshift linearly with laser power indicating gradual heating of the sample proportional to the absorbed power. However, with increasing power the shift was found to saturate at levels that depend on the metal and the contact area. This saturation was attributed to gradual increase of the contact area and improvement of the thermal contacts between the nanostructures and metal electrode that can occur during sample heating. The maximum sample temperature in the beginning of the annealing process was always higher for MW samples, due to smaller area of contact established between rigid multi-layer graphene and initially rough metal surface. The final result is the increased heat losses to the electrodes and, subsequently, the reduction of the samples temperature. The main advantage of this method, when compared with traditional and rapid thermal annealing, is that the thermal treatment is localized in a small pre-determined region, allowing individually controlled annealing process.