The arrangement, first announced in July, offers a revenue opportunity for both companies. But they'll need to convince people to use the search feature, and it's uncertain they will in its current form.

"I'm not sure the experience they offer is optimal," said Greg Sterling, an analyst at Sterling Market Intelligence.

Still, the deal is a coup for Microsoft, which has been struggling to boost its search business. It might be the biggest search agreement for Microsoft in terms of potential users, Sterling said. Microsoft owns a stake in Facebook and has an existing exclusive agreement with the site for banner advertisements.

Starting Tuesday, Facebook users began to notice that when they start typing in the search bar on Facebook, a drop-down menu appears and they can choose to search Facebook or search the Web. If they choose the Web, results appear on a new Facebook page, with advertisements on the right of the screen.

At the top of the results list is a link to do an "Advanced search on Live.com," which launches a new window with results displayed at Live.com. Those results are sometimes slightly different from the ones on the Facebook page and include the ability to expand a search to include images, news, maps and videos.