Google yesterday warned "a couple of million machines" were infected with a form of malware the web giant has been tracking.
Hundreds of thousands more look set to be contacted in the coming days.
"The malware appears to have gotten onto users' computers from one of roughly a hundred variants of fake anti-virus, or 'fake AV' software that has been in circulation for a while," said Google security engineer Damian Menscher, in a blog post.
"We aren't aware of a common name for the malware."
Google said it discovered the infections after detecting "unusual search traffic" whilst carrying out maintenance on one of its data centres.
"This particular malware causes infected computers to send traffic to Google through a small number of intermediary servers called proxies," Menscher said.
"We hope that by taking steps to notify users whose traffic is coming through these proxies, we can help them update their anti-virus software and remove the infections."
Google also sought to allay fears cyber criminals would copy the warning banner in order to dupe web users into clicking through and sending them to a malicious website.
"We thought about this, too, which is why the notice appears only at the top of our search results page," Menscher added.
"Falsifying the message on this page would require prior compromise of that computer, so the notice is not a risk to additional users."
