In a huge blow to the struggling internet pioneer, Yahoo said it made the discovery as it was investigating what was already the largest data breach of a single company.
"Yahoo believes an unauthorized third party, in August 2013, stole data associated with more than one billion user accounts," it said in a statement.
Yahoo said this case "is likely distinct from the incident the company disclosed on September 22, 2016" affecting 500 million users.
The news poses a fresh threat to Yahoo's deal to sell its core operating assets to Verizon for $4.8 billion.
Yahoo says at least 500m accounts hacked in 2014
In November, Yahoo disclosed that as part of its investigation into the prior breach, it had received data files from law enforcement "that a third party claimed was Yahoo user data."
Using outside forensic experts, Yahoo now confirms that this was indeed user data but added that it "has not been able to identify the intrusion associated with this theft."
The statement added that "Yahoo has taken steps to secure user accounts and is working closely with law enforcement."
Yahoo's chief security officer Bob Lord said in a blog post that some of the intrusions were done by hackers who accessed accounts without a password by using "forged cookies," or data files which verify a device or user.
"We believe an unauthorized third party accessed our proprietary code to learn how to forge cookies," he said, adding that "we have connected some of this activity to the same state-sponsored actor believed to be responsible for the data theft the company disclosed on September 22."
Yahoo also said it was requiring affected users to change their passwords, and had invalidated unencrypted security questions and answers.
Yahoo said in September it believed the breach of information on 500 million users was "state sponsored" but some analysts have questioned this theory.
The stolen user account information in the newly disclosed breach may have included names, email addresses, telephone numbers, dates of birth, "hashed" passwords and, in some cases, encrypted or unencrypted security questions and answers, Yahoo said.
Yahoo pressed to explain huge 'state sponsored' hack
The hackers did not obtain passwords in clear text, payment card data, or bank account information, it said.
The latest breach discovery is a further embarrassment to a company that was one of the biggest names of the internet but which has failed to keep up with rising stars such as Google and Facebook.
Steve Grobman, chief technical officer at Intel Security, said the two incidents show "there were clear weaknesses in the architecture" used by Yahoo but that such hacks are not just about technology.
Large organizations holding vast amounts of user data, Grobman said, "need to rely not just on technology but use independent or internal resources to defend against attack scenarios."
Grobman said Yahoo can recover from the debacle but that "it needs to be transparent and show that it will emerge with the best security."
Patrick Moorhead, analyst at Moor Insights & Strategy, said it is possible the disclosure will kill the tie-up with Verizon.
"In the end it will be determined by how Yahoo customers react and what Verizon thinks about this," Moorhead said.
"I don't think Yahoo is worth nearly as much as it was before these two breaches because they can no longer be trusted. Yahoo can build back trust but it will take investment and focus."
Yahoo, after a series of reorganizations, decided late last year to sell its main operating business as a way to separate that from its more valuable stake in Chinese internet giant Alibaba.
Yahoo's plan would place its main operating business within Verizon, which has already acquired another faded internet star, AOL.
The remaining portion would be a holding company with stakes in Alibaba and Yahoo Japan.
Yahoo denies surveillance claims amid privacy outcry
Verizon said in a statement late Wednesday that it would await further news of the investigation before making any decision.
"As we've said all along, we will evaluate the situation as Yahoo continues its investigation," the statement said.
"We will review the impact of this new development before reaching any final conclusions."
Verizon had said the prior breach was likely "material," meaning it could allow the telecom giant to scrap the deal or lower its offer.
Yahoo's valuation hit $125 billion during the dot-com boom, but it has been losing ground since then despite several efforts to reboot.
In the mid-1990s, Yahoo was among the most popular destinations on the internet, helping many people navigate the emerging web.
It became the top online "portal," connecting users to news, music and other content. But its fortunes started to fade when Google began to dominate with its powerful search engine.
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ