Nitrogen-doped vertically aligned multi-walled carbon nanotubes (N-VAMWCNTs) were prepared by reacting fluorinated VAMWCNTs with ammonia gas at temperatures of 300–600 °C. The N-VAMWCNTs were characterized using scanning electron microscopy, high-resolution transmission electron microscopy, X-ray photoelectron spectroscopy, and Raman scattering spectroscopy. In addition, the electrochemical properties of capacitors with N-VAMWCNT electrodes were evaluated by cyclic voltammetry and AC impedance spectroscopy using a two-electrode coin-type cell in an electrolyte of propylene carbonate containing triethylmethylammonium tetrafluoroborate. All the samples were prepared without destroying the alignment structure of the nanotubes. The ratios between the concentration of fluorine, carbon, and nitrogen (F/C and N/F) and the R value (degree of crystallinity) of the samples indicate that the N-VAMWCNTs prepared at 500 °C (N500-VAMWCNTs) had the highest level of nitrogen doping and the best crystallinity among the samples. Nitrogen atoms were doped at a concentration of 5.26 at% into the nanotube frames, thus enriching the N500-VAMWCNTs with pyridinic nitrogen species. The average specific capacitance of the N500-VAMWCNT electrodes was 12.0 F/g at a scan rate of 100 mV/s, which is approximately 1.8 times the value obtained for the as-grown VAMWCNT electrodes (6.5 F/g).