Starmer gave way to a demand by the opposition Conservatives that the government publish information on how Mandelson was appointed.
But he sought to narrow the scope of documents to be released, saying he would not publish any that could be prejudicial to national security or international relations.
Mandelson, a government minister when Starmer's Labour Party was last in power more than 15 years ago, quit the House of Lords on Tuesday over links to Epstein, and is now under police investigation for alleged misconduct in office.
Files released by the US Justice Department last week include emails suggesting Mandelson had leaked government documents to Epstein, and that Epstein had recorded payments to Mandelson or his then-partner, now husband.
Mandelson has said he does not recall having received payments.
He has not commented publicly on the allegations he leaked documents, and did not respond to messages seeking comment.
Starmer defended his own response, saying he had moved quickly to strip all titles and roles from a man he accused of "betraying" the United Kingdom.
But Starmer's explanation of how Mandelson was appointed did little to quieten opposition voices, who said the ambassador's selection in late 2024 put a question mark over the judgment of Starmer and his closest adviser Morgan McSweeney.
"I am as angry as anyone about what Mandelson has been up to. The disclosures that have been made this week of him passing sensitive information at the height of the response to the 2008 financial crash is utterly shocking and appalling," Starmer told a rowdy session of parliament.
"He has betrayed our country, he's lied repeatedly, he's responsible for a litany of deceit. But this moment demands not just anger but action and that's why we've moved quickly," he said after telling MPs he had agreed with King Charles to remove Mandelson from the sovereign's formal body of advisers.
Parliament was due to vote later on Wednesday on the release of documents related to Mandelson's appointment.
Starmer appointed Mandelson in late 2024, arguing that Mandelson's past work in the governments of Tony Blair and Gordon Brown and as the European Union's trade commissioner made him an ideal person to navigate relations with the US under President Donald Trump.
Starmer sacked Mandelson in September after seven months in the job, when documents emerged showing Mandelson had remained close to Epstein after the financier was found guilty in 2008 of child sex crimes.
Emails released last week appeared to indicate that in 2009 Mandelson sent Epstein a memo written for Brown about possible UK asset sales and tax changes, and in 2010 gave Epstein advance notice of a 500-billion-euro ($A839 billion) bailout by the EU.
On Tuesday, Starmer's government passed a dossier about Mandelson to police, who launched an investigation into Mandelson over alleged misconduct in public office.
"The Metropolitan Police have been in touch with my office this morning to raise issues about anything that would prejudice their investigations," Starmer told parliament.
"We are in discussion with them about that."
Other messages in the US files appeared to show Mandelson celebrating Epstein's release from jail as "Liberation day" and how they exchanged sleazy jokes.
One email thread from July 2009 apparently shows the then-government minister asking Epstein how they should celebrate his release from prison after serving 13 months for soliciting prostitution with a minor.
Epstein responded: "With grace and modesty (those are the names of two strippers)."
Mandelson said: "From now on, grace and modesty sd be discovered in London."
Mandelson reportedly told the Daily Mail the messages were his but "they are his (Epstein's) observations not mine" and that he was saying Epstein "should find grace and modesty not strippers".
The 2009 emails also show Mandelson asking "How is freedom feeling?", to which the sex offender replied: "she feels fresh, firm, and creamy".
"Naughty boy," Mandelson wrote in response.
In another message Lord Mandelson can be seen telling Epstein upon his release: "Liberation day ! X."
The crude messages have prompted disgust from political figures, with SNP Westminster leader Stephen Flynn writing on X: "Sick bastards."
with PA
