The removal of nitrogen from coal tar pitch (CTP) through the hydrodenitrogenation (HDN) of CTP and its molecular behavior were evaluated in the presence of NiMo/γ-alumina and CoMo/γ-alumina catalysts. Fourier transform ion cyclotron resonance mass spectrometry with atmospheric pressure photoionization was used to analyze the complicated chemical classes and species of CTP and the treated products at the molecular level. Nitrogen species were qualitatively analyzed before and after hydrotreatment. A single-stage hydrotreatment with an HDN catalyst resulted in a high sulfur removal performance (85.6–94.7%) but a low nitrogen removal performance (26.8–29.2%). Based on relative abundance analyses of nitrogen and binary nitrogen species, C_cH_h-N_nS_s was the most challenging species to remove during HDN treatment. Furthermore, prior hydrodesulfurization was combined with HDN treatment, and the dual hydrotreatments yielded a significantly improved nitrogen removal performance (46.4–48.7%).