The deal only applies to the US and Canada at the moment and US authorities have said they will investigate it, but it is likely that European authorities would also examine the deal if it were extended to the EU.
The agreement allows Google to serve adverts next to Yahoo! search engine results. The deal is non-exclusive and will see Google ads used next to Yahoo! results for certain pre-chosen search terms.
Yahoo! will choose which terms will be served by Google. It said that the two systems competed heavily on common words, but that Google's system produced better results for infrequently searched-for terms.
The deal raises competition concerns because Google and Yahoo! are competitors in the internet advertising market. Google has 68% of the US search market and Yahoo! is dominant in the market for internet display ads.
Aware of the competition law sensitivities the companies have left a window of three-and-a-half months for the US Department of Justice to investigate the deal for competition law irregularities.
The US Senate's Antitrust Committee will investigate the deal, its chairman Herb Kohl said.
"This collaboration between two technology giants and direct competitors for internet advertising and search services raises important competition concerns. The consequences for advertisers and consumers could be far-reaching and warrant careful review, and we plan to investigate the competitive and privacy implications of this deal further in the Antitrust Subcommittee," he said.
But the final word on the deal will rest with the Department of Justice (DoJ), which will assess whether or not the move restricts competition too heavily in a market in which Google is already the strongest company.
Experts say that the crucial factor in the DoJ's analysis will be the definition of the market in which the companies are said to operate. Google has little market power in the whole advertising market, more in the internet advertising market and an enormous amount in the internet search market. The outcome of the probe is likely to depend on which market definition is chosen.
Analyst Blair Levin of Stifel Nicolaus told investors in a note that another key issue will be whether or not Yahoo! maintains full operation of its own system, Panama.
"We believe the companies need to do a better job than they did on yesterday's calls [to press and analysts outlining the deal] to answer the question why the efficiencies of the deal won't ultimately lead advertisers to move to Google, leaving Yahoo without a viable search advertising product and Google as the only search advertising game in town," Levin said in his note.
Competition law expert Edward Anderson of Pinsent Masons, the law firm behind OUT-LAW.COM, said that it is no accident that the deal is being trialed first in the US and Canada.
"The European competition authorities have a reputation for being more adverse to deals between companies with large market shares than their American counterparts, who are typically more easily convinced by arguments of efficiency," he said.
"Google and Yahoo! may have decided to test the waters in North America before Europe because if the North American authorities object to the deal it is unlikely that European regulators would approve of it," said Anderson.
Anderson said that the crucial question in Europe would also be what the regulators chose to define as the market in which Yahoo! and Google's ad services compete.
"If implemented in the EU, the big issue will be how the European competition authorities define the market, because this determines market shares and what competitive constraints exist on the parties; the wider the market, the lower the market shares and the more possible constraints and less chance of competition problems," he said.
Yahoo!, Google and Microsoft have been embroiled in complex corporate machinations in recent months. Microsoft offered to buy Yahoo! but was rebuffed, and then made an offer to buy 16% of the company last week.
Google objected to the deal, claiming that the resulting merged company would be anti-competitive.
Now that the Google-Yahoo! tie up has been made public, Microsoft says it believes that deal to be anti-competitive.
"Our position has been clear since April that any deal between these two companies will increase prices for advertisers and start to consolidate more than 90% of the search advertising market in Google's hands," Microsoft spokesman Jack Evans told CNET News. "Legal and industry experts agree that this would clearly make the market less competitive."