America's second most senior law official said the allegation was "inaccurate and factually incorrect".
The New York Times, citing anonymous sources, also said Mr Rosenstein had suggested secretly recording Mr Trump to expose chaos in the White House.
But a source told the BBC that the comment was sarcastic.
Mr Rosenstein is reported to have made the remarks after Mr Trump fired the FBI director last year.
James Comey had been overseeing his law enforcement agency's investigation into alleged ties between the Trump campaign and Russia. Mr Trump referred to the "Russia thing" when asked why he was removed.
What is the claim?
The New York Times reported that Mr Rosenstein had discussed recruiting cabinet members to invoke the 25th amendment of the US constitution, which provides for the removal of a president if he is deemed unfit for office.
It also says he suggested secretly recording Mr Trump to expose White House turmoil and dysfunction.
The suggestions came during meetings and conversations in May 2017 with Department of Justice and FBI officials, the paper said.
It cited several unnamed sources who were briefed on the events.
According to US media, the source of the allegations are memos created by former FBI acting director Andrew McCabe, who was fired by Mr Trump in March this year.
Mr McCabe's lawyer, Michael Bromwich, said his client "has no knowledge of how any member of the media obtained those memos".
Mr Bromwich said the memos had been submitted to the special counsel who is investigating possible Russian meddling in the 2016 election and obstruction of justice, and that another copy had remained with the FBI.
How did Mr Rosenstein respond?
The deputy attorney general issued a statement saying: "The New York Times's story is inaccurate and factually incorrect.
"I will not further comment on a story based on anonymous sources who are obviously biased against the department and are advancing their own personal agenda.
"But let me be clear about this: Based on my personal dealings with the president, there is no basis to invoke the 25th amendment."
Who's telling the truth?
A justice department press officer told the BBC that Mr Rosenstein's comment about secretly recording the president was a joke.
The statement was attributed to "a source who was in the room" and was said to remember the exchange in question.
"The statement was sarcastic and was never discussed with any intention of recording a conversation with the president," the unnamed source said.
The spokesperson did not immediately reply to an emailed question asking if the 25th amendment was discussed during that meeting.
In other US media, there was scepticism that the US deputy attorney general would earnestly propose ousting the president.
Activating the relevant section of the 25th amendment would require a majority of Mr Trump's cabinet, the vice-president and majorities in Congress, which is currently controlled by the president's party.
The Washington Post also reported that Mr Rosenstein's remark about surreptitious recordings was not serious.
The newspaper said the deputy attorney general had been responding to Andrew McCabe's suggestion that the justice department investigate the president.
According to the Post, Mr Rosenstein replied sarcastically: "What do you want to do, Andy, wire the president?"
The newspaper also said that someone who was present at the meeting denied the 25th amendment had ever come up.
Will Trump sack Rosenstein?
Donald Trump has spent a lot of time disparaging "fake news" reports from the "failing" New York Times largely based on anonymous sources. It will be interesting to see how he responds to an article that seemingly confirms his suspicions that members of his own administration are out to get him.
Or maybe they're not. It all depends on whether you believe sources who talked to people who were in the room when Rod Rosenstein reportedly entertained notions of secretly taping the president or organising a constitutional manoeuvre to remove Mr Trump from office.
On some level, it doesn't matter if the reports are true. They alter events and perceptions either way. Mr Rosenstein has been on thin ice with the president for so long his feet probably have frostbite. The New York Times story could be the ominous crack that presages a plunge into the cold abyss.
Given Mr Rosenstein's position overseeing Robert Mueller and the Russia probe, any move against him by the president would be fraught with political peril. The president has vowed that he won't make a decision about Jeff Sessions until after the mid-term elections in November. Would that reluctance extend to the attorney general's second in command?
Timeline of events
9 May 2017 - Deputy Attorney General Rod Rosenstein submits a memo to the attorney general regarding FBI boss James Comey's investigation into Hillary Clinton's handling of classified documents. President Trump fires Mr Comey, and Andrew McCabe becomes acting director of the FBI.
11 May 2017 - Mr Rosenstein denies that he threatened to quit after being described as a key influence in Mr Comey's firing. The New York Times says Mr McCabe's memos from around this time note that Mr Rosenstein was upset and wished Mr Comey was still at the FBI.
16 May 2017 - Mr Rosenstein met Mr McCabe and other senior officials to explain his role in Mr Comey's firing. He reportedly said he was frustrated with Mr Trump, suggested wearing a "wire" to secretly record the president during White House visits, and discussed invoking the 25th amendment to oust Mr Trump for being "unfit" for office, the New York Times reported on Friday.
17 May 2017 - Mr Rosenstein appoints Robert Mueller as special counsel, tasked with overseeing the Russia investigation.
17 March 2018 - Mr McCabe is fired by Mr Trump a day before his planned 18 March retirement. He had stepped down from his FBI role amid relentless criticism from Mr Trump.
30 May 2018 - US media report that Mr McCabe handed over a confidential memo on Mr Comey's firing - which reportedly details his conversation with Mr Rosenstein - to the special counsel.
26 July 2018 - After the justice department rejects a request to release Mr McCabe's memos, conservatives in the House of Representatives file articles of impeachment in an effort to oust Mr Rosenstein, accusing him of stonewalling their requests for information, which he denies. Read Full Story