This morning “bing” became the sound of a done deal between Microsoft and Yahoo. A long and tumultuous negotiation between the two has finally come to a close, one that will see the two companies combine their search businesses to take on Google. Microsoft’s new Bing search engine will power both company’s services on search and Yahoo will take leadership on ad sales. Together they will represent about 30% of the market, placing them a distant second behind Google, but with the hope that the combined resources will be enough to gain more ground.

“Success in search requires both innovation and scale. With our new Bing search platform, we’ve created breakthrough innovation and features” said Microsoft Chief Executive Officer Steve Ballmer. “This agreement with Yahoo! will provide the scale we need to deliver even more rapid advances in relevancy and usefulness. Microsoft and Yahoo! know there’s so much more that search could be. This agreement gives us the scale and resources to create the future of search.”

Microsoft’s need for Yahoo’s market share and resources drove them towards an attempted $44 billion acquisition of the company last year, one that despite the lucrative gain was turned down by Yahoo co-founder Jerry Yang leading to a massive upheaval within Yahoo as shareholders scrambled to recover the deal.

As the year passed, the economy was hit by recession, Yahoo’s stocks began to fall and the ensuing chaos through the company into disarray. Many financial market watchers focused on Yahoo over Microsoft as the one in most need of a deal between the two, something Microsoft took advantage of as it began to suggest it was no longer interested in the company, that it had a “plan B”, with other companies and technologies it could acquire to achieve the same results.

As today’s announcement supports, Microsoft has always needed Yahoo. After trailing in the search market for years, Microsoft invested millions of dollars and years of development to re-launch MSN Search as Windows Live Search complete with a whole new search engine. Their market share stayed the same and it became clear that most users will use a Google product simply because its “Google” and amongst those immune to such an attraction, they’d rather use Yahoo than use a “Microsoft” product.

Changing perception has been Microsoft’s hardest challenge. The plan was always to re-launch their service as “Bing” to put more of a friendlier distance from their own brand and to focus its services onto the needs of casual users, namely Yahoo’s core audience.

Has last year’s acquisition gone through, Microsoft would have been able to launch Bing as a Microsoft-Yahoo effort and leverage Yahoo’s good will to market it.

Time has passed and with the ouster of Yahoo co-founder Jerry Yang from the company’s control, the new Chief Executive Office Carol Bartz has managed to help form a partnership with Microsoft instead, one that will help lift Yahoo’s profits even if it doesn’t give the company’s shareholders the windfall they had hoped for.

The deal still has to gain regulatory approval and scrutiny by the industry before it can move forward, a process that Microsoft and Yahoo executives say could take months. For Microsoft and Yahoo users, the change won’t be felt until next year.

The challenge for Microsoft moving forward will be to win over Yahoo’s users with Bing, a process that would have been easier before the two companies joined together. While Bing’s focused tools on health, travel, shopping, and local search are bound to have an appeal, it’s perception as a Microsoft service may drive users back to Google.

If Yahoo users can be tempted to join Microsoft’s current audience in championing Bing, then the search engine may just earn enough of a positive reputation to force even the die-hard Google users to give it a try.