Оснивачки конгрес Нове комунистичке партије Југославије (НКПЈ) одржан је 30. јуна 1990. године у Београду. Конгрес (Оснивачка скупштина) је одржан у сали Савеза инжињера и техничара Србије, уз учешће 265 делегата из свих република Социјалистичке Федеративне Републике Југославије. Присутни делегати су донели одлука да Партија добије име Нови комунистички покрет Југославије (НКПЈ). То име је било актуелно све до 1995. године, када је промењено у данашње, Нова комунистичка партија Југославије (НКПЈ).
На Првом конгресу одлучено је да највиши орган НКПЈ буде Виши политички савет, а његов извршни орган Секретаријат. На Конгресу, и нешто касније, изабрани су и кооптирани у Секретаријат: Бранислав – Бранко Китановић, Александар Јовановић, Драгутин Вукићевић, Радоња Вешовић, Живан – Џина Радовановић, Васо Ивановић, Михајло Реновчевић, Милан Николић, Веселин Поповић, Петар Шушњар, Владимир Ивановић, Адем Омеркић, Миливоје Стефановић – Долински, Милојко Лукић, Божо Делибашић, Радомир Мрдаковић, Радоица Таутовић, Нада Крајгер, Владимир Андрејевић, Мирчета Серталић, и по још један члан из Хрватске и Македоније. Касније је у Секретаријат коптиран Властимир Јовановић. За генералног секретара НКПЈ изабран је Бранко Китановић а за председника Радоња Вешовић.
У фебруару 1991.године осмочлана делегација НКПЈ била је гост Комунистичке партије Совјетског Савеза (КПСС) на позив чланова руководства КПСС који су били противници издајничке линије Горбачова Јаковљева и Шеварнадзеа.
У јануара 1993. основан је Савез комунистичке омладине Југославије (СКОЈ) као настављач револуционарних и слободарских традиција некадашњег СКОЈ-а који је укинут 1948. године.
Други конгрес НКПЈ одржан је у Београду априла 1991. године у Педагошкој академији. На конгресу је дошло до оштрог генералног сукоба између марксистичко-лењинистичке линије огромне већине чланова Партије и Секретаријата и социјал-демократске и каријеристичке оријентације изразите мањине. Конгрес се завршио поразом социјал-демократске и каријеристичке групе која је била принуђена да напусти Партију. У тој групи је био и председник Радоња Вешовић. Након његовог изласка из Партије нико више није биран на функцију председника (која је у пракси имала почасни карактер) а касније је изменама избачена из Статута НКПЈ.
На априлском пленуму 1992.године одлучено је да НКПЈ успостави контакт са обе комунистичке партије које су формиране у Русији после распада СССР-а крајем 1991.године. После тога у Москву је отпутовала делегација НКПЈ предвођена генералним секретаром Бранком Китановићем, која је успоставила сарадњу са руским ком-партијама.
У фебруару 1993.године делегација НКПЈ учествовала је у Пјонгјангу (ДНР Кореја) на конференцији комунистичких партија из целог света. На конференцији НКПЈ је потписала заједничку декларацију у којој су изнете оцене о разбијању СССР-а и социјализма у Источној Европи.
Крајем фебруара 1993. године представници НКПЈ као једини страни делегати, присуствовали су у Москви на Оснивачком конгресу Комунистичке партије Руске Федерације (КПРФ). На локалним изборима у мају 1992. године НКПЈ осваја једно одборничко место у Скупшини општине Пожаревац. На децембарским општим изборима исте године, на којима је учествовала и про-империјалистичка буржоаска опозиција која је бојкотовала опште мајске изборе, НКПЈ осваја два одборника у Скупштини општине Пожаревац. На годишњој конференцији 21. децембра 1995. године усвојени су нови Статут и Програм НКПЈ. На савезним изборима 1996. године (избори за Веће грађана Скупштине СР Југославије) у изборној јединици Зрењанин НКПЈ осваја око 11.000 гласова и Партији за длаку измиче улазак у савезни парламент. Незванично се спекулисало да је НКПЈ која није имала свог представника у изборној комисији изборне јединице Зрењанин добила већи број гласова од званично саопштеног, односно да је изборила улазак у Скупштину СРЈ, то јест да су Партији гласови покрадени. Носилац изборне листе у Зрењанину, члан Централног комитета НКПЈ друг Слободан Милошев је освојио одборнички мандат у Скупштини општине Нова Црња. С обзиром да је НКПЈ прихватила коалицију са Социјалистичком партијом Србије (СПС) која није могла самостално да формира власт у Новој Црњи, Милошев је изабран на функцију потпредседника Скупштине општине Нова Црња.
У марту 1997. године излази први број листа “Нови комунист”, органа Централног комитета Нове комунистичке партије Југославије. Трећи конгрес Партије одржан је 1. априла 2001. године у Београду, у Немањиној 34, где су се налазиле тадашње просторије НКПЈ. На конгресу је усвојена Резолуција у којој се констатује да је у земљи извршена контрареволуција, уз спрегу империјалиста и домаћих реакционарних снага.
Период од 5. октобра 2000. године за НКПЈ представља најтежи период у постојању јер је Партија изложена готово потпуној информативној блокади и бројним дискриминацијама. Велики ударац за Партију представља и одузимање просторија у Немањиној 34 у мају 2011. године у којима је НКПЈ боравио од јула 1991. године. Тадашњи буржоаски про-империјалистички режим Демократске странке сматрао је да ће одузимањем просторија НКПЈ умртвити рад комуниста у периоду светске капиталистичке кризе, међутим Партија је владајућој експлоататорској класи показала да је “тврд орах” успешно наставивши са деловањем из нове центале у Устаничкој 17. Ненадокнадив губитак НКПЈ је претрпела у децембру исте године када је из њених борбених редова смрт истргла оснивача и првог генералног секретара Партије друга Бранка Китановића. Иако тешко погођена ненадоместивим губитком друга Китановића једног од најуваженијих и најпризнатијих лидера међународног комунистичког покрета, Партија је неуморно наставила да корача путем који је зацртао њен оснивач. У јануару 2012. године одржана је успешна годишња конференција НКПЈ под називом “Настављамо линију, јачамо Партију” на којој је изабрано ново руководство.