CNBC reported this morning that in a call with analysts, Microsoft SVP Satya Nadella announced that the company has reached a web search and search advertising agreement with Facebook. Microsoft PR says the deal will go live by the end of the year.

This is a big announcement, as Facebook has to date provided no web search to users. Facebook and Microsoft will work together to design the best integration of Microsoft’s Live Search service for Facebook’s users.

Late last year, Microsoft made a $240 million strategic investment in Facebook at a stratospheric $15 billion valuation. As part of that deal, Microsoft gained rights to sell Facebook’s US and global ad inventory. Since that time, there has been much speculation as to whether the agreement would extend into search.

Now that the Yahoo deal has seemingly fallen apart, Microsoft is even more eager to expand its search footprint against arch rival Google. Google reached a large search agreement with MySpace a few years ago, guaranteeing $900 million in payments over 3.75 years. Since that time, there have been rumors that Google has been dissatisfied with the monetization performance of MySpace’s search traffic.

We’ll see if things turn out differently for Microsoft and Facebook.