Il fonda le Parti vert démocratique en août 2009 pour constituer une opposition démocratique et écologiste au Front patriotique rwandais, le parti au pouvoir. La plupart des membres fondateurs du Parti vert étaient des dissidents qui avaient quitté le FPR[2].
En mars 2010, Habineza fut l'un des « invités d’honneur de l’université africaine des Verts » à Rabat, dans le cadre d'une coordination des partis et des mouvements écologistes africains[3]. Le mois suivant, il fut nommé président du Comité exécutif de la Fédération des Verts africains[4].
Le Parti vert n'ayant pas été officiellement reconnu par les autorités rwandaises, il ne put pas prendre part à l'élection présidentielle d'août 2010. Il lui a également été impossible d'obtenir l'autorisation nécessaire pour ses réunions, et en octobre 2009 l'une de ses réunions fut dispersée par la police. Plusieurs de ses membres ont été menacés, et incités à abandonner leurs activités politiques ; certains l'ont fait[2]. Le 4 février 2010, Habineza lui-même fut abordé dans un restaurant à Kigali par un inconnu, qui lui demanda pourquoi les Verts avaient rejeté le FPR, et l'avertit : « Nous te surveillons de très près. Fais attention »[5]. En juin, le gouvernement l'accusa d'escroquerie - accusation relayée par la presse explicitement pro-Kagame, telle le New Times[6]. Le journal Focus Media publia un article le ridiculisant et suggérant qu'il était motivé uniquement par la soif du pouvoir[1]. En juillet 2010, le vice-président du parti, André Kagwa Rwisereka, fut retrouvé décapité. Habineza demanda une enquête internationale indépendante[7],[8]. Personne n'est arrêté pour ce crime[9].
En 2013, le Parti vert est enfin formellement autorisé et reconnu par les autorités - trop tard pour pouvoir participer aux élections législatives cette année-là[9]. En mars 2017, le parti investit Frank Habineza comme candidat à l'élection présidentielle du mois d'août[10]. En juillet, sa candidature est approuvée par la commission électorale[11]. C'est la première fois de l'histoire du pays qu'un parti d'opposition est autorisé à participer à une élection présidentielle[12]. Il recueille 0,48 % des voix[13].
Lors des élections législatives de 2018, le Parti vert obtient deux sièges à la Chambre des députés, dont un pour Frank Habineza. C'est la première fois, sous l'ère Kagame, qu'un parti d'opposition est représenté au Parlement[14].
