Działalność polityczna W drugiej połowie lat 80. XX w. został członkiem Movimiento de Participación Popular (MPP, Ruch Powszechnego Uczestnictwa), partii politycznej, która stała się największą frakcją lewicowej koalicji Szeroki Front (FA, Frente Amplio).
W 1995 objął fotel deputowanego w Izbie Reprezentantów, a w 1999 został senatorem. W wyborach parlamentarnych z 31 października 2004 uzyskał reelekcję w Senacie. Nie objął jednak urzędu, gdyż 1 marca 2005 prezydent Tabaré Vázquez mianował go ministrem hodowli zwierząt, rolnictwa i rybołówstwa w swoim gabinecie. 3 marca 2008 zrezygnował ze stanowiska ministra i objął w tym samym dniu mandat senatora.
14 grudnia 2008 Mujica został wybrany na jednego z pięciu kandydatów Szerokiego Frontu w prawyborach prezydenckich. W głosowaniu uzyskał największą liczbę głosów. W prawyborach 28 czerwca 2009 zdobył 54,1% głosów poparcia i pokonał swojego głównego rywala Danilo Astoriego, zostając tym samym oficjalnym kandydatem Szerokiego Frontu w wyborach prezydenckich w październiku 2009. 11 lipca 2009 wybrał Astoriego swoim kandydatem na stanowisko wiceprezydenta kraju. Mujica uważany był za faworyta w wyścigu wyborczym.