Mujica var tidigare senator och jordbruks- och fiskeminister i företrädaren Tabaré Vázquez regering. Han var en av ledarna för Tupamarosgerillan MLN (Movimiento de Liberación Nacional), som bekämpade militärdiktaturen i Uruguay 1973–85. För sin politiska aktivitet, där bland annat bankrån ingick, satt han fängslad i 14 år, ett par av dem i isoleringscell.