NKPJ je nastala na osnivačkom kongresu [[30. lipnja]] [[1990.]]. u [[Beograd]]u. Kongres je održan u sali Saveza inženjera i tehničara Srbije, uz sudjelovanje 265 delegata iz svih republika SFRJ. S obzirom da se tadašnja vlast protivila nazivu ''Komunistička partija'', na kongresu je odlučeno da se napravi kompromis i prihvati ime ''Novi komunistički pokret Jugoslavije''. Krajem 1990. vlast je dopustila naziv ''Komunistička partija'', ali iz praktičnih i administrativnih razloga naziv ''Komunistički pokret'' ostao je služben do [[1995.]]. godine.
Na Prvom kongresu odlučeno je da najviši organ NKPJ bude Viši politički savjet, a njegov izvršni organ Tajništvo.
U veljači [[1991.]]. osmočlana delegacija NKPJ bila je gost [[Komunistička partija Sovjetskog Saveza|Komunističke partije Sovjetskog Saveza]] na poziv članova rukovodstva KPSS koji su bili protivnici linije [[Mihail Gorbačov|Gorbačova]] - Jakovljeva i Ševarnadzea.
Drugi kongres NKPJ održan je u Beogradu travnja 1991. godine. Na kongresu je došlo do sukoba između marksističko - lenjinističke većine i socijaldemokratske manjine.
Na travanjskom plenumu [[1992.]]. odlučeno je da NKPJ uspostavi kontakt sa obje komunističke stranke formirane u [[Rusija|Rusiji]] poslije raspada [[SSSR]]-a krajem 1991. Poslije toga je u [[Moskva|Moskvu]] otputovala delegacija NKPJ predvođena Brankom Kitanovićem. Uspostavili su suradnju sa ruskim komunistima.
U siječnju [[1993.]]. osnovan je [[Savez komunističke omladine Jugoslavije]], nastavljač tradicija SKOJ-a ukinutog godine [[1948.]].
U veljači 1993. delegacija NKPJ sudjelovala je u [[Pjongjang]]u (DNR Koreja) na konferenciji komunističkih stranaka iz cijelog svijeta. Na konferenciji NKPJ je potpisala zajedničku deklaraciju u kojoj su iznijete ocjene o razbijanju SSSR-a i socijalizma u istočnoj [[Europa|Europi]].
