The former Prime Minister yesterday rejected accusations he talked of "waging war" on the Murdoch empire after The Sun newspaper switched allegiance to the Tories before the 2010 General Election.
Mr Brown told the inquiry into press standards the alleged phone call had never taken place and that when the two men did speak, months later, it was to discuss Afghanistan.
However, Mr Murdoch, who testified under oath that the threat had taken place when he gave evidence in April, last night issued a statement saying he stood by his evidence.
During more than two-and-a-half hours of testimony, Mr Brown also insisted he had never "authorised" aides to brief against cabinet colleagues including Tony Blair and Alistair Darling.
He rejected evidence from former Sun editor and News International chief executive Rebekah Brooks that he and his wife Sarah had authorised a story about their baby son Fraser's medical condition in 2006.
In April, over two days at the inquiry, Mr Murdoch, the News Corporation chief executive and Sun owner, said he had received the furious phone call from Mr Brown in September 2009.
He told the inquiry: "I don't think he (Mr Brown) was in a very balanced state of mind".
However, Mr Brown released official Downing Street records yesterday which he said proved the only phone conversation between the two men during the period took place in November.
The former Labour leader said: "I couldn't be unbalanced on a call that I didn't have, and a threat that was not made."
Mr Brown said there was "not one shred of evidence that a call took place."
Last night, News Corporation said Mr Murdoch did not intend to back down over his claims.
A spokesman said: "Rupert Murdoch stands behind his testimony."
Mr Brown also denied during evidence claims he and his wife had given permission for a newspaper story that revealed their son suffered from cystic fibrosis. He said they had been presented with a "fait accompli" and told the story was about to appear.
There "was no question of us being willing, complicit or ... desiring that this information become public," he said.
Last month, in her evidence, Mrs Brooks said she did have the express permission of the couple to run the story, something the Browns immediately disputed.
However, Mr Brown did admit that a "forgiving" Sarah had stayed friendly with Mrs Brooks afterwards, and he felt it was his duty as a senior politician to keep in touch with the editor. In wide-ranging testimony, Mr Brown also denied "authorising" briefing against senior colleagues. Asked whether his aides had been part of attempts to force Tony Blair to step down as Prime Minister, he said: "I would hope not. I've got no evidence of that."
Asked about ex-Chancellor Alistair Darling's suspicions that he was being briefed against in office, Mr Brown said there were always "gossip, rumour, (and) innuendo" around Westminster.
However, he added: "Nobody in my position would have instructed any briefing against a senior minister, and Alistair Darling was a friend of mine as well as a colleague."
Last night Tory MP Louise Mensch said his claim not to have been involved in briefing against others "undermines all of his testimony".
Mr Brown also told the inquiry The Sun had decided to back the Tories because they were more amenable to his corporation's commercial aims
Chancellor George Osborne later told the Leveson Inquiry that allegations of a deal with the Murdochs were a "complete nonsense".