1999 йылда Дәүләт Думаһына һайлауҙарҙа Тулеев КПРФ исемлегенә инә, әммә Кузбасста Берҙәмлекте хуплай. 2000 йылда НПСР-ҙан сығарыла. 2003 йылдың декабрендә «Берҙәм Рәсәй» төбәк исемлеген етәкләй, һөҙөмтәлә партия Кемерово өлкәһендә . Кемерово өлкәһе халыҡ депутаттары советының барлыҡ 35 депутаты ла Тулеев ярҙамы менән ойошторлған «Кузбассҡа хеҙмәт итәм» блогынан һайланған.