The state government's State of the Environment report said the two species were found on Cape York, in tropical far north Queensland.
"The Rhaphidospora cavernarum, which is a large herb that stands about one and a half metres high, has reappeared," state climate change minister Andrew McNamara told Australian Broadcasting Corp radio.
"It hasn't been seen in Queensland since 1873," he said.
He said the second plant that has reappeared, another herb called Teucrium ajugaceum, was last seen in 1891.
The report was produced from research by more than 100 academic and government experts.
"The rediscovery of two presumed extinct plant species has seen a decline in this category, with a corresponding increase in the endangered category," the report said.
It said more than 50 plant species new to science are discovered and described in Queensland every year and there are more than 12 000 native plant species known to science in the state.
Reporting by Victoria Thieberger; Editing by Jerry Norton