A 1958 national plebiscite elected Stroessner to a second term, but dissatisfaction with the regime blossomed into a guerrilla insurgency soon afterward. Sponsored by exiled Liberals and Febreristas, small bands of armed men began to slip across the border from Argentina. Venezuela sent large amounts of aid to these groups starting in 1958. The following year, the new Cuban government under Fidel Castro Ruz also provided assistance.

Stroessner's response was to employ the state's virtually unlimited power by giving a free hand to the military and to Minister of Interior Edgar Ynsfrán, who began to harass, terrorize, and occasionally murder family members of the regime's foes. A cycle of terror and counter-terror began to make life in Paraguay precarious.

The guerrillas received little support from Paraguay's conservative peasantry. The Colorado Party's peasant py nandí irregulars ("barefoot ones" in Guaraní), who had a welldeserved reputation for ferocity, often tortured and executed their prisoners. Growing numbers of people were interned in jungle concentration camps. Army troops and police smashed striking labor unions by taking over their organizations and arresting their leaders.

In April 1959, however, Stroessner grudgingly decided to heed the growing call for reform within the army and the Colorado Party. He lifted the state of siege, allowed opposition exiles to return, ended press censorship, freed political prisoners, and promised to rewrite the 1940 constitution.