W wyborach parlamentarnych w 1995 KPFR uzyskała już największe poparcie spośród wszystkich partii (22,30% głosów). Tym razem partia wprowadziła do parlamentu aż 157 deputowanych. W wyborach prezydenckich w 1996 kandydatem KPFR został jej lider, Giennadij Ziuganow. W I turze wyborów zajął drugie miejsce zdobywając 32,5% głosów. W II turze Ziuganow otrzymał 40,7% głosów, przegrywając z Borysem Jelcynem, który uzyskał prezydencką reelekcję. W wyborach parlamentarnych w 1999 KPFR po raz kolejny uzyskała największy wynik wyborczy (24,29% wszystkich głosów), tym razem wprowadzając 113 deputowanych do Dumy Państwowej FR.
W wyborach prezydenckich w 2000 po raz kolejny kandydatem partii został Giennadij Ziuganow. Uzyskał on 21 928 471 głosów w skali kraju (29,5% poparcia), zajmując drugie miejsce i przegrywając z Władimirem Putinem. W wyborach parlamentarnych w 2003 partia zajęła drugie miejsce (za Jedną Rosją), tracąc jednak znacznie poparcie. KPFR uzyskała 12,6% poparcia i wprowadziła jedynie 58 deputowanych do parlamentu. W wyborach prezydenckich w 2004 kandydatem wystawionym przez KPFR został Nikołaj Charitonow (popierany również przez Agrarną Partię Rosji). Uzyskał on 13,69% poparcia, zajmując drugie miejsce.