Becali dat piept cu politica pentru prima oară în 2000 când a candidat din partea unei formaţiuni a italienilor pentru Camera Deputaţilor. N-a fost să fie, dar nu a renunţat. În 2004 a preluat Partidul Noua Generaţie, (PNG), de la fostul primar Viorel Lis şi i-a adăugat şi o codiţă creştină (Creştin Democrat).
Eşecul din acel an la prezidenţiale, când a reuşit un scor de doar 1, 77% nu l-a descurajat. Dimpotrivă, Becali a crescut în sondaje cât alţii în ani, asta şi graţie succeselor înregistrate de Steaua în cupele europene: 10-15% pentru partid, cote de încredere de 30% pentru el, erau cifre obişnuite în anii 2006-2007. A fost momentul în care, partidul s-a aflat sub bagheta din umbră a „profesorului” de politică al lui Becali, Dan Pavel, în jurul acestuia gravitând jurnalişti, istorici. Pavel însă a plecat, dar a rămas prieten cu milionarul.
Scandalul cu Hagi l-a costat scump în 2007 pe Becali. Nu doar fotbalistic, ci inclusiv politic. După nici două luni de la momentul la care l-a instalat pe fostul decar al Naţionalei pe scaunul de antrenor al trupei din Ghencea, \"Războinicul Luminii\" l-a executat public, într-un scandal presărat cu amănunte despre viaţa intimă a acestuia. \"Hagi a fost un nume mare, dar Gigi Becali i-a luat tot, dar absolut tot: onoare, demnitate, personalitate, minte, tot, tot, tot”, a mărturisit “Regele”, atunci.
Latifundiarul - care la acel moment estima că are o avere de 3 miliarde de euro – a pierdut rapid nu doar susţinerea suporterilor roş-albaştrii care l-au demonizat întruna de atunci ci şi pe cea a alegătorilor: în două luni procentele sale s-au topit vâzând cu ochii, nici sprijinul unei părţi însemnate a înalţilor ierarhi ai BOR – care au primit donaţii generoase de la acesta pentru biserici – nemaicontând.
Şampania victoriei la eurorparlamentarelor din 2007 a rămas nedesfăcută în palatul din Aleea Alexandru, PNG obţinând puţin sub pragul electoral de 5%. Un mai târziu în vară, PNG reuşea însă să intre în Consiliul General al Muncipiului Bucureşti şi graţie unei alianţe cu PD-L, să obţină un scaun de viceprimar.
Toamna lui 2008 a fost una însă extrem de agitată. Iar patronul Stelei a pierdut în faţa Oanei Niculescu-Mizil scaunul de deputat, PNG ratând total uninominalele. Se certase între timp cu Patriarhia, după ce solicitase ca aceasta să-i restituie donaţia de 2 milioane de dolari pe care o oferise pentru ridicarea Catedralei Mântuirii Neamului, şi mai mult, s-a aflat că era în litigiu cu o mănăstire din Pipera pentru un teren. Scandalul a atins apogeul când familia Becali a încercat să intre pe teren cu buldozerul.
Din arestul poliţiei, în Parlamentul European
Cel care i-a relansat cariera politică a lui Becali a fost liderul PRM Corneliu Vadim Tudor. A fost un serviciu reciproc pe care cei doi lideri şi l-au făcut. Vadim Tudor a întrezărit potenţialul electoral şi mediatic pe care îl are Becali, aflat în arestul poliţiei în Rahova, după ce a fost acuzat că i-ar fi sechestrat pe cei care i-au furat maşina, şi l-a convins să candideze pe listele PRM pentru Parlamentul European. A fost probabil mişcarea care a readus PRM din nou în prim-plan, după ce eşuase să intre în Parlamentul României în toamna lui 2008, la uninominale. Formaţiunea lui Vadim Tudor a obţinut trei mandate, scor nesperat, pentru Vadim Tudor, Becali şi pentru Claudiu Tănăsescu. Chiar dacă, imediat, după ce a ieşit din puşcărie, Becali a declarat că nu are de gând să mai facă politică, s-a răzgândit în doi timpi şi trei mişcări, şi a revenit la mai vechea sa dorinţă de a candida la prezidenţiale.
Amicul de şpriţuri de odinioară, preşedintele Traian Băsescu, i-a devenit principala ţintă, în contextul în care Becali a preluat o parte din temele de campanie ale PSD: cota progresivă de impozitare, susţinerea pentru Adrian Severin pentru scaunul de ministru de externe al UE etc. Un semn că relaţia de prietenie dintre Viorel Hrebenciuc şi Becali se face simţită.