Microsoft has beat out Google to become the default search provider on all phones on the Verizon Wireless network.

Steve Ballmer made the announcement to a packed hall as part of his keynote address at the 2009 Consumer Electronics Show in Las Vegas recently.

Starting in the first half of 2009, Microsoft (MSFT, Fortune 500) will power all search on Verizon Wireless devices and serve up the advertising.

The five-year deal is strategically critical to Microsoft, which didn’t yet have a search deal in the United States. Competitor Yahoo (YHOO, Fortune 500) powers AT&T and T-Mobile and Google (GOOG, Fortune 500) is the search provider for Sprint. That’s why Microsoft has fought so hard to wrangle the deal from the reigning search giant.