Harlow unveiled her latest effort, two sleek new phones built atop the latest version of Microsoft’s mobile platform, Windows 8, in early September in the wake of the chaos and confusion surrounding a jury verdict that found that No. 1 smartphone maker Samsung had infringed on several Apple patents. Analysts believe Apple (AAPL) will be emboldened by its win to sue other phonemakers, and while some observers have suggested that Microsoft-fueled phones may not be in Apple’s cross hairs, one thing is clear: The ruling will push handset companies to differentiate their products from the iPhone. But can beleaguered Nokia (NOK), which largely missed the consumer shift to smart devices, deliver phones that are innovative enough to unseat Apple?

MORE: Stephen Elop’s mission impossible

Harlow, who was tapped in July 2010 by Elop to run the smartphone business, certainly thinks so. She offered Fortune an inside look at the steps she has taken to bring Nokia’s newest smartphone line to market, starting with the Lumia 800 and the Lumia 710, released worldwide in the fall of 2011. “Becoming cool again means having great products,” she says. Her first step: to show Microsoft (MSFT) some love. To make sure the teams were in sync, she rearranged her organization to match her partner’s Windows Phone unit structure. “I can trust her with what she tells me,” confirms Terry Myerson, the Microsoft vice president who heads the Windows Phone division. “She uses that same direct and genuine communication to motivate her team.”

Even as she was building bridges with Microsoft, Harlow was dismantling other operations, including teams that had been working on Nokia’s internal operating system, Symbian, which lost out to Windows Phone. She says her most difficult day at Nokia was going out to the company’s office in Farnborough, England, to lay off hundreds of engineers. “A big part of my job at that time was restructuring the organization that would remain,” says Harlow. “It was a huge challenge, but I believed so strongly that this was the route to a great future for Nokia.”

It is too soon to know whether Nokia’s smartphone strategy is a hit, but the handset maker has scored some small, early wins. Under Harlow’s watchful eye, her team has met its production targets and even won some plaudits. Last quarter Nokia shipped 4 million Lumia phones, double the number it sold the quarter before. Tech blog CNET.com praised the Lumia 800’s “innovative design” and “gorgeous screen” but complained about the device’s camera and video quality. The newest Lumia devices pack some impressive features — especially the 4.6-inch Lumia 920, which comes with a souped-up camera that lets users take pictures in low-light settings (see image at the bottom).

Harlow says Nokia can play to its strength and differentiate Lumia smartphones with innovations in location-based services (it owns mapping provider Navteq), imaging, and hardware design, including the use of new materials.

Nokia’s biggest ally in its turnaround — Microsoft — is also its potential Achilles’ heel. Nokia’s exclusive relationship with Microsoft makes life a lot simpler for the device maker. It needs to build phones for only one platform, and there’s no question that Microsoft gives Nokia special treatment. The tech giant, based in Redmond, Wash., was more than willing to let the phonemaker help “drive and define” the future of the Windows Phone operating system and kicked in money to seal the deal. Microsoft is paying Nokia quarterly “platform support” payments that started with $250 million in the fourth quarter of 2011. (It helps that Elop spent almost three years at the software giant.) And there’s evidence that the strategy works: Motorola Mobility revived its smartphone business by committing to Google’s Android platform. Then it got bought by Google (GOOG).

But unlike Android, which has a robust following among developers and consumers, devices that run on Windows Phone account for just 3.5% of the global smartphone market, according to research firm IDC.

And there are many analysts who believe a device maker needs its own operating system (think of it as the brains of the phone) à la the iPhone and the iPhone OS — that’s the only way to control quality and make sure the product is truly differentiated from rivals. Indeed, while Nokia has a tight relationship with Microsoft, it is far from exclusive: Other phonemakers, including Samsung and HTC, are expected to launch their own Windows 8 phones in the coming months. And more may jump on the Windows bandwagon as a “safer” alternative to Android while the market sorts out the impact of the Samsung ruling.

Nokia made a very conscious choice to outsource its operating platform when it killed off Symbian — amazingly, at Harlow’s recommendation. In fact, Harlow was running Symbian at the time, and her willingness to sacrifice her own business was one of the things that impressed Elop.

MORE: New battle-lines in the war for mobile

Still, the 49-year-old Kentucky native is an unlikely candidate to drive the company’s new smartphone strategy. She has a degree in psychology, not business or engineering, and worked marketing roles at Reebok and Procter & Gamble (PG) before heading to Nokia in 2003 and eventually making the jump to product management. Former Nokia executives, accustomed to managers with technical backgrounds, have griped that she may not be suited for the role.

But Elop is clearly a fan. “She’s been given opportunities along the way to be in roles for which she is uniquely unqualified and yet has the people skills, the intellectual capacity, and the intellectual integrity to actually drive successes,” he says.

Inside Nokia, Harlow is known for her strong personality. But at a recent interview with Fortune in New York, the former captain of Duke University’s women’s basketball team comes across as thoughtful and soft-spoken, not domineering. With a team spread across several locations — San Diego, Beijing, Taiwan, Bristol, and three sites in Finland — she spends at least 75% of her time on the road.

She nonetheless finds time to study and collect wine; her home, just south of London, houses a collection with some 2,000 bottles. “I have a very nice 2000 Bordeaux that I’ve been saving for the Windows 8 announcement,” says Harlow. “But a lot of what I have won’t be ready to drink for another two to three years.” By that time, we’ll probably have a better sense of whether Nokia’s transformation — and Harlow’s leadership — will be reason to celebrate.

This story is from the September 24, 2012 issue of Fortune.

[cnnmoney-video vid=/video/technology/2012/09/05/nokias-uphill-battle-with-smartphones.fortune]