Il partito fece il suo debutto alle elezioni parlamentari del 1994, in cui si attestò come la prima forza politica del Paese conseguendo il 13,57% dei voti e 86 seggi alla Verchovna Rada. Mantenne la maggioranza relativa dei voti alle elezioni parlamentari del 1998, quando raggiunse il 24,65% ottenendo 122 seggi.
Nel 2000 alcune componenti lasciarono il partito dando vita a due diverse formazioni, il «Partito Comunista dell'Ucraina (rinnovato)» (KPU(o)) e il «Partito Comunista degli Operai e dei Contadini» (KPRS). Secondo il KPU, la creazione di tali soggetti politici sarebbe stata sostenuta dal Presidente Leonid Kučma per togliere voti al KPU.[1]
Alle elezioni parlamentari del 2006 il Partito delle Regioni (PR) ottenne la maggioranza relativa dei voti, mentre il KPU crollò al 3,67%. Le posizioni dei due blocchi filo-occidentale e filo-russo rimasero sostanzialmente inalterate: si verificò soltanto una polarizzazione verso il PR nel campo filo-russo e verso il Blocco di Julija Tymošenko nel campo filo-occidentale. Dopo il breve governo della Tymošenko, la guida dell'esecutivo passò a Janukovyč, sostenuto anche dal KPU; si aprì successivamente una grave crisi politica, al termine della quale furono indette nuove elezioni.
Alle elezioni parlamentari del 2007 i comunisti ottennero il 5,39% e 27 deputati, collocandosi all'opposizione del governo guidato dalla Tymošenko.
Alle elezioni politiche del 2012 il KPU ottenne un forte aumento di voti giungendo al 13,18% (+7,8%) dei consensi e 32 seggi, risultato parzialmente penalizzato nell'assegnazione dei seggi dal passaggio da un sistema proporzionale ad uno misto proporzionale-maggioritario.
Nel 2022 Petro Simonenko, presidente del partito prima che venisse bandito, ha sostenuto l'invasione su larga scala dell'Ucraina, sostenendo che "per proteggere i propri cittadini e garantire la sicurezza nazionale, la Russia non aveva altra scelta se non quella di sferrare un attacco preventivo".[4]