But what ultimately saved Brennan, the longest-held Australian hostage outside of a war situation, were the efforts of his family, who refused to give up on him and took the lead in negotiations to secure his release.
"If it wasn't for my family I would still be in captivity. They decided to move away from the government and take matters into their own hands," said Brennan at the launch of The Price of Life, a book about his kidnapping and ransom, this week.
Somalia has been mired in violence and awash with weapons since the overthrow of a dictator in 1991. The weak western-backed government controls only parts of Mogadishu, the capital.
Just days after arriving, Brennan and Canadian documentary maker Amanda Lindhout were kidnapped and held for $3.16m - money their families had to come up with, since neither the Australian nor Canadian government will ransom their citizens.
Knowing their relatives could not pay that money, the two converted to Islam on the suggestion of one captor that their lives might be spared if they did so - resulting in days filled with religious instruction, regular prayers, and reading an English version of the Qur'an.
Refuge in mosque
Escape attempts came to nothing, with one try failing when Lindhout couldn't manage to slip through the bars of a window.
The two the next day managed to slip into a nearby mosque.
"We knew it would be full and we could get help from the Muslim community," Brennan said.
But just as they got into the mosque a warning shot rang out over their heads and pandemonium broke out. They were soon surrounded by gun-wielding men.
"Amanda was dragged out and about 20 seconds later I heard a single gunshot fired and actually believed she'd been killed," Brennan said.
Brennan himself was pistol-whipped, kicked to the ground and punched and thought he would be killed on the spot. Mysteriously spared, the next ten months until their release were filled with near-starvation, and they were kept shackled.
Freedom
Back in Australia, Brennan's sister Nicky became the main hostage negotiator, with coaching from the Australian police. Eventually, with the aid of an Australian businessman, all came together and roughly $650 000 was paid for Brennan.
After 462 days in captivity, the two were freed.
Despite his ordeal, Brennan says he would still go back to the war-torn nation, where local journalists are still suffering, if things stabilised. Somali legislators on Tuesday approved a new prime minister.
"I would really love to see an improvement in Somalia. I would love to see the world media take a little bit more action in what's happening because local journos are being killed like flies," he added.