When Caxias arrived at the allied camp in November 1866, he found something closer to a refugee settlement than a fighting force. A cholera epidemic had killed or incapacitated thousands; the word itself was banned from official communications to prevent panic. Soldiers drank water from wells contaminated by poorly buried corpses. One Brazilian veteran recalled digging a hole in his tent floor to cool a water jug: a single stroke of the hoe exposed a rotting skull. The cavalry had no horses. Infantry rifles lacked ramrods. Many soldiers had traded away their uniforms and walked barefoot. The 1st and 2nd Brazilian Army Corps ran such different administrative systems that Caxias said they "seemed to belong to two different nations." New recruits were being handed guns and sent into battle without a single day of training.

Caxias took fourteen months to rebuild the army before resuming offensive operations, enduring mockery from the Brazilian press for his caution. He isolated cholera patients, instituted sanitation inspections, and created a Field Police Inspectorate to enforce hygiene standards. He purchased 5,000 modern breech-loading Roberts rifles and 2,000 Spencer repeating rifles from the United States, then established a training program to teach soldiers how to use them. New recruits received fifteen days of drill before being issued weapons. Horses and mules were bought and properly fed with alfalfa and corn instead of the local vegetation that had been killing them. When the British explorer Sir Richard Burton visited a Brazilian camp near Humaita in August 1868, he was stunned by the transformation: "Before he took charge, the Brazilian army was in the worst possible condition; now it can compare favourably as regards the appliances of civilization with the most civilized."

Rather than repeat the suicidal frontal assault of Curupayty, Caxias adopted a plan to encircle Humaita from the landward side while Brazilian ironclads forced the river passage. On July 22, 1867, some 38,500 men marched out of the camp at Tuyuti toward a settlement called Tuyu-Cue -- meaning "mud-that-used-to-be" in Guarani. The name was accurate. The route crossed both branches of the Estero Bellaco, a sedge marsh so dense and waterlogged that the 28-mile detour took ten days. Supply convoys threaded through marshland on a 70-kilometer line that could have been cut at any point by a determined Paraguayan strike. Meanwhile, ten Brazilian ironclads dashed past the guns of Curupayty in August, losing only 3 sailors killed, and began sinking the pontoons that held up Humaita's chain boom. By October, Brazilian cavalry discovered Potrero Obella, the secret cattle pen feeding the garrison, and captured it after fierce fighting.

Inside the fortress, the Paraguayan garrison endured conditions that defied comprehension. The marshy soil could not grow manioc or maize. Salt was nearly unobtainable, causing lethargy and weakness in men already weakened by dysentery. Cholera swept the Paraguayan lines as well. A British diplomat who passed through in September 1867 reported seeing boy soldiers, a claim confirmed by a Lopez decree from that March. George Thompson observed that the corpses of Paraguayan soldiers were so emaciated they would not decompose, instead drying into mummies where they fell. And yet they fought on with a ferocity that awed even their enemies. When a shell killed a Paraguayan soldier in the midst of his comrades, Thompson wrote, they would "yell with delight, thinking it a capital joke, in which they would have been joined by the victim himself had he been capable."

Lopez, recognizing that encirclement was inevitable, ordered something no one had attempted before: a 54-mile road hacked through the Gran Chaco, the desolate wilderness on the opposite bank of the Paraguay River. The road crossed five deep streams and the Bermejo River, passing through terrain so hostile that only the indigenous Toba people inhabited it. Cattle had to swim the 500-yard-wide river to reach the road, and many drowned until pontoons were built. When Humaita finally fell on July 26, 1868, the defenders did not surrender. Lopez used his Chaco road and two paddle steamers to evacuate the bulk of his army to fight another day. The allies entered the fortress to find earthworks, empty gun emplacements, and the ruins of what had been, for two and a half years, the most stubborn obstacle any South American army had ever faced.