The alert is displayed on google.com and only appears to users whose search traffic is redirected through specific IP addresses associated with this threat.
"This particular malware causes infected computers to send traffic to Google through a small number of intermediary servers called proxies.
"We hope that by taking steps to notify users whose traffic is coming through these proxies we can help them update their antivirus software and remove the infections" Google said.
According to the company the malware was identified after unusual traffic patterns were detected during a routine maintenance operation.
The search giant contacted the companies from where the traffic originated and established that their computers were infected with a click fraud trojan.
Routing search traffic through proxy servers gives attackers the ability to manipulate the responses. Usually this is used to introduce ads that generate income for fraudsters into the search results.
The warning affected users see when opening Google Search reads: "It appears that your computer is infected with software that intercepts your connection to Google and other sites." It contains a link which takes users to a help document which provides instructions on how to deal with the problem.
Google is usually very careful with the changes it makes to its search site and favors a minimal design. Therefore the decision to add this notification is an important decision for the company.
"We're trying this as an experiment to alert and protect consumers that we believe have infected machines. Please share this widely," said Matt Cutts the head of Google's anti spam team.
It's not clear if the company plans to use the same method to warn about future threats as well but it's hard to tell how they would be able to determine infected users in other situations.