W lipcu 1992 parlament albański przyjął ustawę zabraniającą działalności partii komunistycznej w Albanii. Kolejną próbę legalizacji partii podjęto w lipcu 1996. Pod zarzutem „nielegalnego kolekcjonowania materiałów zagrażających porządkowi konstytucyjnemu i próby stworzenia partii komunistycznej” aresztowano czterech działaczy (Sami Meta, Kristaq Mosko, Timoshenko Pekmezi i Tare Isufi)ATA News from Albania, 96-07-29.. Partia doczekała się legalizacji w 1998, kiedy władzę objęła Socjalistyczna Partia Albanii.
W wyborach parlamentarnych 2005 KPA uzyskała 8901 głosów (0,7%). W 2008 działacze partii zorganizowali szereg wieców dla uczczenia 100 rocznicy urodzin Envera Hodży, domagając się referendum dotyczącego odbudowy jego pomników, zniszczonych w latach dziewięćdziesiątych. Skandalem zakończyły się uroczystości w rodzinnej miejscowości Hodży – Gjirokastrze, gdzie działaczy partii nie wpuścił do domu syn Envera, Ilir Hodża, uważany za sympatyka Socjalistycznej Partii AlbaniiSherr në Gjirokastër,djali i Enverit përzë nga shtëpia Hysni Milloshin.. W wyborach parlamentarnych 2009 partia nie brała udziału.
W 2002 doszło do podziału w łonie partii i wyłonienia się ugrupowania o nazwie Albańska Partia Pracy.