El partit va néixer al 2004 després de la celebració d'un 10è Congrés alternatiu del Partit Comunista, agrupant grups dissidents en l'anomenat "Congrés de Patriotes de Rússia".[1] Aquests el van constituir oficialment aprofitant l'estructura d'un partit minoritari del 2002 anomenat Partit Laborista,[2] modificant el nom a Patriotes de Rússia en el seu 2n Congrés en el qual Gennadi Semigin va ser elegit president.
Poc després de la seva fundació, al 2006, els Patriotes es van unir a la facció Rodina a la Duma. Però fruit de tensions internes i diferències polítiques, un cop la coalició es va transformar en Rússia Justa, van declarar la seva intenció de retirar-se del nou partit i presentar-se a les eleccions de 2007, en les quals obtindrien només 639,119 vots i prop de l'1%, sense cap representació a la Duma. A les següents eleccions legislatives van mantenir resultats, però a les de 2016 van veure reduït el seu suport en gairebé la meitat respecte les anteriors, amb 310.015 vots i el 0.59%. A nivell presidencial van donar suport a Vladímir Putin a les eleccions de 2012 i 2018.[3]
Més endavant, el 22 de febrer de 2021, el partit retornaria a Rússia Justa refundant-la amb el nom Rússia Justa: Patriotes, per la veritat[4].