In a separate letter from Deputy Attorney General Rod Rosenstein, the Justice Department set out a brutally frank case that Comey had repeatedly bungled the handling of the Hillary Clinton email matter.
"I cannot defend the Director's handling of the conclusion of the investigation of Secretary Clinton's emails, and I do not understand his refusal to accept the nearly universal judgment that he was mistaken," wrote Rosenstein.
"Almost everyone agrees that the Director made serious mistakes; it is one of the few issues that unites people of diverse perspectives," Rosenstein added.
The announcement was made minutes after the FBI released a letter clarifying testimony that Comey had given to Congress last week, centering on the investigation into Hillary Clinton's emails; his testimony had overstated the number of emails possibly found on a computer belonging to ex-Rep. Anthony Weiner (D-NY), the husband of top Clinton aide Huma Abedin.
The news stunned official Washington, as Democrats immediately questioned whether it was an attempt to rein in investigations that could impact the White House.
"Comey should be immediately called to testify in an open hearing about the status of Russia/Trump investigation at the time he was fired," said Sen. Ron Wyden (D-OR).
"Donald Trump's own Saturday Night Massacre," said Rep. Tim Ryan (D-OH), referring to Watergate.
"We need an independent investigation," said Sen. Tom Udall (D-NM).
"Now it is more clear than ever that we need an independent commission to get to the truth of Russia’s interference with our election," said Sen. Bill Nelson (D-FL).
On the other side of the aisle, most Republicans backed the President's move.
"Best. Termination. Letter. Ever," tweeted Rep. Lynn Cheney (R-WY).
"The handling of the Clinton email investigation is a clear example of how Comey's decisions have called into question the trust and political independence of the FBI," said Sen. Charles Grassley (R-IA).
"Many, including myself have questioned his actions more than once over the last year," said Sen. Roy Blunt (R-MO) of Comey.
But there were some Republicans who disagreed with the move, like Sen. John McCain (R-AZ), who labeled it, "disappointing."
Sen. Bob Corker (R-TN) echoed those worries - even as he acknowledged the missteps by Comey - saying Comey's "removal at this particular time will raise questions."
"His dismissal, I believe, is a loss for the Bureau and the nation," said Sen. Richard Burr (R-NC), the Chairman of the Senate Intelligence Committee.
One Republican raised questions about the President's own letter to Comey, which noted how the former FBI chief had assured Mr. Trump that he was not the target of any investigation.
"The second paragraph of this letter is bizarre," said Rep. Justin Amash (R-MI).
Comey was confirmed as FBI Director in September of 2013; he was to have served a ten year term until 2023.
Earlier this year, during a speech in Boston, Comey gave no sign that he was going to leave early.
"You're stuck with me for about another six and a half years," he said.
Two months later, Comey was out of a job.
"I wish you the best of luck in your future endeavors," the President wrote.