W latach 1996-1997 Payá współtworzył szkic Projektu Varela http://www.proyectovarela.org i http://www.mclpaya.org/ ogłoszonego oficjalnie 22 stycznia 1998 r. w Hawanie. Nazwa nawiązuje do Felixa Varela, księdza i kubańskiego bohatera, żyjącego w latach 1788-1853, walczącego przeciw Hiszpanom, którzy wtedy panowali na Kubie.

Projekt Varela przypomina próby działaczy opozycji w Niemczech Wschodnich i ZSRR w latach 70-tych odwoływania się do istniejącego prawa międzynarodowego, z zastrzeżeniem, że celem ich nie jest „obalanie ustroju siłą”, ale egzekwowanie tego, do czego zobowiązały się rządy m.in. obradując na Konferencji Bezpieczeństwa i Współpracy w Europie zobowiązały się do przestrzegania praw człowieka.

Projekt wykorzystuje „lukę” w kubańskiej konstytucji, która przewiduje instytucję referendum powszechnego oraz możliwość wniesienie przez 10 tys. obywateli propozycji ustawy (artykuł 88 Konstytucji Kubańskiej). Pomysłodawcy Projektu Varela postanowili skorzystać z tego prawa i ogłoszono w 1998 r. inicjatywę zbierania podpisów. 10 maja 2002 r. zebrano 11 200 podpisów pod petycją ( udokumentowanych numerem dowodu osobistego podpisujących, co w warunkach kubańskich wydawało się niemożliwe) domagając się przeprowadzenia referendum. W tym referendum Kubańczycy mieliby się wypowiedzieć, czy chcą demokratyzacji oraz reform gospodarczych (m.in. wolnych wyborów, respektowania wolności słowa, uwolnienia więźniów politycznych, swobody stowarzyszeń, wolności przedsiębiorczości, która do tej pory była zagwarantowana jedynie dla cudzoziemców) . Projekt przedstawiono Z gromadzeniu Narodowemu. Wokół jego poparcia zebrało się ponad 200 osobistości z różnych kręgów ideologicznych znanych jako grupa Wszyscy Zjednoczeni (Todos Unidos).

Rząd Kubański kilkakrotnie próbował stłumić tą inicjatywę m.in. podważając autentyczność podpisów, ogłaszając osobiście przez Fidela Castro w lipcu 2002 r. przesunięcie „na czas nieokreślony” kolejnych obrady Zgromadzenia Narodowego, które powinno zająć się petycją, aż do ogłoszenia w styczniu 2003 r., iż projekt ten jest sprzeczny z podstawowymi zasadami konstytucji. Konsekwencją tych działań opozycyjnych były aresztowania 1 8 marca 2003 r. 75 liderów obywatelskich, niezależnych dziennikarzy i działaczy związkowych. Pomimo tych represji Payá i inni działacze kontynuowali rozpoczętą inicjatywę i zebrano października 2003 r. dodatkowe 14 384 podpisy pod petycja.

Projekt Varela miał bardzo ważny skutek, gdyż zintegrował część środowisk opozycyjnych - druga część z nich jest przeciwna działaniom podejmowanym na bazie komunistycznego prawa. Zwróciła też uwagę na zmęczenie społeczeństwa kryzysem gospodarczym, na postulaty uchylenia amerykańskiego embarga, nawiązanie z USA współpracy gospodarczej i przywrócenie ruch turystycznego, co może pomóc Kubie wyjść z kryzysu.