Following the demise earlier today of negotiations to merge or partner with Microsoft, Yahoo has announced it has entered into a non-exclusive partnership with Google to run the search giant’s ads alongside its own search results and on some of its websites in the United States and Canada.

Yahoo expects the deal to raise revenue by $800 million in its first year and to provide an extra $250 million to $450 million in incremental operating cash flow. The partnership with Google was largely expected after the company failed to reach an agreement with Microsoft, and will hopefully (for Yahoo at least) help stave off a campaign by billionaire shareholder, Carl Icahn, to unseat the company’s board.

For Microsoft it is back to square one, it seems, on their ongoing quest to challenge Google’s dominance in the lucrative search advertising space. I wouldn’t be surprised to see them raise antitrust concerns over the Yahoo / Google deal.