Yahoo and Finland-based Nokia Monday announced a deal to build Yahoo e-mail, search, and other applications and services into a range of the mobile phone maker's devices.

The partnership is being dubbed "Project Nike" after the Greek goddess of victory. The deal has been quietly in the works for years as Google and Apple have garnered much of the action in the burgeoning smartphone market.

Some Nokia devices already have Yahoo services preloaded. This new partnership extends that relationship so that Yahoo's e-mail and instant-messaging services will now be integrated with Nokia's Ovi Internet platform. Nokia will now be the exclusive provider of Yahoo's maps and navigation services, and will integrate Ovi Maps into Yahoo services.

Yahoo is the number one provider of webmail across the U.S, ahead of Microsoft's Windows Live/Hotmail, and Gmail.

Products will be branded with "Powered by Ovi." Yahoo will also power Nokia's Ovi Mail and Ovi Chat services, and those services will be branded "Powered by Yahoo." The two companies plan to allow customers to use their Ovi or Yahoo user IDs to log into accounts.

Yahoo CEO Carol Bartz said the deal is not exclusive and that Yahoo will continue to work with other cell phone manufacturers for integration into other smartphone operating systems. This means that Yahoo will remain on Research In Motion's BlackBerry devices, Apple's iPhone, and Google Android devices.

Olli-Pekka Kallasvuo, CEO of Nokia, said the deal will help the company gain a stronger standing in the U.S. market. He acknowledged that the company has been struggling to keep up the pace of innovation in the North American market. While Nokia leads worldwide in the overall cell phone market and also in the growing segment of smartphones, it has lagged in the United States.

While the pair had once discussed Nokia making a Yahoo-centric phone, it was not clear Monday whether that will be part of this deal. Yahoo has had a range of various mobile initiatives along with many, mostly unsuccessful, partnerships with carriers and telecom makers. Because the Internet giant has not developed its own phone or mobile operating system, it has lost traction in what has become the most important digital sector today.

The two companies did not disclose the financial terms of the deal. Nokia recently announced a management reorganization which paired its Ovi application services in the same business unit as its Symbian and MeeGo operating systems.