The soldiers sleep in tents, hidden from roaming lions by a blind, and protected by high-powered rifles that also ward off the even more dangerous threat of poachers.
173 rhinos have been poached throughout South Africa to date, of which 120 were poached in Kruger National Park.
In April, South African soldiers were deployed in Kruger National Park to safeguard the border with Mozambique, where heavily armed and highly organised poachers have driven the slaughter of rhinos to record levels to feed an Asian black market for traditional medicine.
"It's not just a poacher coming in and he's hunting for meat, or he comes in with his snares or he comes in with his darts to hunt with a hunting rifle," said Ken Maggs, a top environmental crimes investigator in the park.
"He's coming prepared to fight. Hence the tactics that we deploy on the ground are military, paramilitary."
The poachers slip across the Mozambican border with night-vision goggles, AK-47s, hunting rifles, and in one case, a grenade. Moving in the dark, they scrawl warnings to rangers in the sand.
The army patrols are the first line of defence. Working with a park ranger, they walk through the bush in the early hours of morning, alert to the threat of both predators and poachers.
One evening, a group of lions lounged just 100 metres (100 yards) from their camp. But the poachers pose a deadlier threat, and haven't hesitated to open fire on the patrols.
Fifteen poachers have been killed in shoot-outs so far this year in Kruger, nine wounded and 64 arrested.
The deterrent seems to be working.
March was the deadliest month for rhinos in Kruger's recorded history, with 40 animals killed for their horns, according to the military. Since the army deployment, the number has steadily dropped, to 30 in April, 15 in May and just two in June.
It's the first, and still cautious, sign of improvement since 2007, when just 13 rhinos were poached in South Africa -- compared to 333 last year.
But success in the park will solve only one part of the problem, with surging demand in Asia, particularly China and Vietnam, to use rhino horns in traditional medicines to treat everything from nosebleeds to fevers.
"The recent poaching crisis has been attributed to an increase in demand in Vietnam, where a new purported use of rhino horn has appeared as a treatment for cancer," said Alona Rivord, spokeswoman for environmental group WWF.
Rhino horns are made of keratin, like human fingernails, and have no scientific medicinal value, but that's done little to curb the black market demand. China has outlawed the use of rhinos in medicine, but enforcement is lax, conservation activists say.
High prices in Asia have led to a more complicated problem: manipulation of South Africa's legal trophy hunts to export rhino horns that end up on the black market.
Black rhino are critically endangered, meaning they're at risk of extinction with only 4,838 left in the world, according to the International Union for Conservation of Nature.
White rhinos are more numerous at 17,480. They are legally hunted in South Africa, with a permit that costs just 50 rand ($7.50, five euros), said Rynette Coetzee, project executive in the law and policy programme of the Endangered Wildlife Trust.
"There's hunting taking place, and it's legal because permits are being issued," she said.
Each hunter is allowed to kill only one rhino each year, but police earlier this month arrested Thai national Chumlong Lemtongthai, accusing him of working with a syndicate to smuggle 40 horns obtained with hunting permits.
He reportedly paid friends and even prostitutes to pose as hunters, and worked with a South African wildlife trader who bought rhinos at auctions, but then killed them soon after they arrived on his farm.
Chumlong reportedly sold the horns for $55,000 per kilo, literally worth their weight in gold.
"They are battling to enforce the legislation" on trophy hunting because wildlife authorities lack the staff and vehicles to do the job, Coetzee said.
Maggs calls corruption within the wildlife business "khaki collar" crime, a problem highlighted when a Kruger ranger was arrested Monday in connection with poaching.
"The involvement of some of the professional people in the industry is of great concern," Maggs said, including professional hunters, veterinarians and game farm owners who "are taking advantage of the high prices being paid for rhino horn and the illegal smuggling of it."