On the morning that Marissa Mayer started her new job as CEO of Yahoo, David Filo waited for his new boss in the lobby of corporate headquarters in Sunnyvale, Calif. As “Chief Yahoo,” Filo is Yahoo’s largest individual shareholder, and the taciturn 48-year-old engineer is the only founder still working at the company. (He sits in a cubicle, where he solves gnarly engineering problems.) Greeting her warmly, he walked her up to her new third-floor office. “I was just trying to do whatever I possibly could do to help her,” he told Fortune recently. Little did Mayer know just how much help she was going to need.

At first blush, Mayer’s nearly two-year tenure at Yahoo seems golden: She has motivated a beleaguered workforce and spent almost $1.3 billion to acquire 36 companies, including the social software startup Tumblr. She has launched a slew of new products, including a weather app that won praise from Apple designer Jony Ive, digital magazines, and mobile versions of Yahoo Screen, the company’s YouTube-like video property. She has hired celebrity journalists like Katie Couric and former New York Times tech writer David Pogue. Mayer has unveiled a rich assortment of high-budget original programs, partnerships, and coverage of live events. And she has finally stopped Yahoo from losing both ad dollars and users.

By another measure, Mayer’s tenure at the company has seemed a resounding success: Yahoo’s stock has more than doubled in value, to around $35. But the stock’s strength has little to do with Mayer’s turnaround efforts. Yahoo owes its lofty valuation to a pair of smart Asian investments. Back in 1996 the company launched Yahoo Japan, a joint venture with Softbank; its 35% stake is worth $9 billion. More significantly, Yahoo owns 24% of the Chinese Internet dynamo Alibaba. It is expected to soon file for an initial public offering that is likely to be the largest tech IPO in history; Yahoo’s share of the company will probably be worth a whopping $40 billion — impressive until you consider that Yahoo’s total market capitalization is $35 billion (for more, see IPO Time for Alibaba). In other words, investors seem to be saying that Yahoo’s core business is worth less than nothing.

And there’s the rub. Mayer can acquire all kinds of cool technology and generate buzz with video programming, but none of that will solve her biggest problem: Yahoo’s advertising business — which generates roughly four-fifths of its sales — is a mess. Yahoo’s share of the global market for digital-ad spending has continued to shrink, while Google maintains a strong lead and Facebook shows impressive growth, according to EMarketer. In January, Mayer fired her top sales guy, an ex-Googler who had been her first major hire as CEO. This spring two of Yahoo’s board members who had the most experience in media and advertising — the chief marketing officer of American Express and the CEO of media company Scripps — announced they would step down. (Yahoo has nominated Filo, former Wal-Mart CEO Lee Scott, and brokerage icon Charles Schwab as directors.) And advertisers complain that the technology behind Yahoo’s tools is archaic. In 2013 revenue fell 6%, to $4.68 billion, and when Fortune unveils its annual ranking of the country’s 500 largest companies next month, Yahoo will not be on the list for the first time in nine years.

Mayer certainly has what it takes to revive Yahoo. At 38, she has both the computer-science cred to quiz Yahoo’s engineers on their most sophisticated algorithms and the star power to woo talent and win the attention of marketing chieftains who would have otherwise delegated Yahoo’s ad buys to their underlings long ago. Most important, Mayer has ambition. As employee No. 20 at Google, where she oversaw many of the company’s most important products, she’s not in this for the paycheck. She wants to build a next-generation tech company focused on mobile experiences, video, and communications that will compete squarely with Google and Facebook. Nothing short of this will do. (Mayer declined to participate in this story, but Yahoo made more than a dozen executives, engineers, and advertisers available to Fortune; separately, Fortune interviewed former employees, shareholders, advertisers, and analysts to gain a full picture of the company’s condition.)

The trouble is that Mayer is strapped (for now) to a terrible business model. If you put aside Google, which dominates search advertising, and Facebook, which owns social, digital advertising isn’t the growth engine that media companies hoped it would be, in part because publishers haven’t reinvented the business proposition: They still attempt to aggregate large audiences and show them display ads. Inventory is growing (because the Internet is, you know, infinite), and as a result, the price that sites can charge for these traditional ads is decreasing from an average cost per thousand impressions of $3 in 2010 to $2.80 in 2013. Marketers are dedicating a smaller chunk of their ad budgets to online display units. And so Yahoo needs to sell even more ads to maintain its current revenue levels.

There is a paradox to the Yahoo story: After watching five years of declining revenues under the disjointed leadership of zigzagging CEOs, many of Yahoo’s investors, analysts, and advertisers have little faith in the ability of the legacy Internet company to regain its momentum. Yet those same constituents harbor an unfounded optimism and nostalgia for the company that helped define the earliest days of the consumer Net. As a result, analysts and advertisers alike are rooting for Mayer to execute a turnaround the likes of which the corporate world hasn’t seen since Lou Gerstner saved IBM.

For Mayer to pull off such a feat she will have to fix — and possibly reinvent — Yahoo’s main business. The good news is that she’ll have the cash to do so if she chooses: Yahoo must sell nearly 40% of its Alibaba stake after the company goes public, a move that will bring in more than $16 billion based on current valuations. Mayer has given little indication of what she plans to do with it. Nor has she indicated that she’s thinking about fundamentally changing Yahoo’s business model. But her actions over the next six months will determine whether one of the charter members of the Internet can rise to dominance again — or whether Mayer will pen its last chapter.

Ramy Adeeb and Eric Vishria, like more than 300 of their fellow engineers, are newcomers to Yahoo, brought in through acquisitions to help the company get its tech mojo back and inject it with some entrepreneurial fervor. They work from adjustable desks on a renovated floor of building D, the executive building, close to Mayer. Adeeb, 35, arrived in January 2013 when Yahoo acquired his company, Snip.it. Digital magazines development, he explained, fell to him. He personally recruited Vishria, 34, who started working on the project the day after Yahoo bought his company, Rockmelt. Adeeb and Vishria report feeling relatively unhindered as they brainstormed designs for one of Yahoo’s spate of new products, digital magazines. Their mockups were bold, as they required Yahoo to shift the way it sold ads, but Mayer was supportive. Says Vishria: “I remember in our CEO review, as we were going through the designs, Marissa said, ‘Wow! That will really change a lot of things. We should try it.'”

The month before Mayer launched the products at the Consumer Electronics Show, Yahoo offered Fortune an early look. Adeeb nodded at Vishria, who spun around his MacBook Air to reveal Yahoo Food, a visually stunning media site powered by software from Tumblr. Unlike Yahoo’s traditional sites, where the audience is measured by page views, these digital magazines present stories in a continually flowing stream, embedding advertising as content. A cookie recipe sponsored by Splenda was tucked in between stories written by Yahoo-employed journalists, as well as pieces pulled from sites like Epicurious and Southern Living. “We will actually change the way advertisers think about an ad,” Adeeb says. “This is something we could have never done at a startup.”

The newly hired engineers are not the only Yahoos feeling energized. Mayer has famously made Yahoo a less bureaucratic place. She ordered a revamp of the 22-page travel-and-expense policy, handed out iPhones, and offered free meals. She got rid of the class that Yahoo employees had to take before they were allowed to use the gym, figuring that, as one new recruit noted, “If you can’t use a treadmill by now, it’s on you.” And she began updating Yahoo’s employees on the business in weekly Friday “FYI” meetings.

And she brought Filo back. She and Filo co-signed the management letter in Yahoo’s 2012 annual report, her first as CEO. The two meet regularly — she changed the org chart so that he reports directly to her — and insiders say she takes his counsel seriously. When one of Yahoo’s potential acquisitions was stalled, the target company’s CEO appealed to Filo. The deal got done that day. Filo and corporate development head Jacqueline Reses have resuscitated a program that brings together the founders now employed by Yahoo, a gesture that has helped underscore the importance of entrepreneurs to Yahoo’s culture.

If Mayer made Yahoo a more entrepreneurial and engaging place to work, she also stepped up the demands on employees’ time. She did away with the work-from-home policy. She has attempted to pare down the workforce through a rigorous quarterly review system, modeled after Google’s, in which top performers receive generous bonuses and the underperformers are dismissed. Her goal is to reduce the 12,400-person workforce — sources close to the company say she initially told the board of plans to trim employees by 35% to 50% — while bolstering talent.

Her management style is far from perfect. She’s notoriously late for meetings, sometimes not showing up at all. And while she has cultivated the perception of accessibility — early on, she would log in to the engineers’ private listserver and start the occasional conversation with an employee many levels down in the organization — she makes more time for the parts of the business that interest her. So while some executives, especially those in new product areas, report that she is engaged and asks questions about the very algorithms that underpin their ideas, others say, “Not so much.”

Mayer, a computer scientist and self-described shy person, didn’t come to Yahoo with the pedigree of some of her predecessors (former CEO Carol Bartz had run a public company) or the media and advertising background of her fellow candidates (Ross Levinsohn ran digital for News Corp.). Her education has come on the job, where her closest colleagues describe her as earnest and uncommonly smart, with a predilection for pattern recognition. At Fortune’s Most Powerful Women Summit, she spoke of her own education, sharing advice she’d received from a fellow CEO. She was more subdued than usual on that October morning. For one thing, she had a cold. Her voice was raspy, and the staccato chortle that punctuates so many of her conversations was nearly absent as she explained, “The interesting thing about being CEO is that you have very few decisions you need to make, and you need to make them absolutely perfectly.”

Certainly nothing in her professional training prepared her for the complexity of dealing with activist investors (even seasoned CEOs can be derailed by them), which makes her handling of Third Point Management’s Dan Loeb all the more impressive. He was the one who unearthed the damning news that her predecessor, CEO Scott Thompson, had lied about having a computer-science degree. As a result, Loeb was named to the board along with two appointees, and he lobbied hard to get Mayer the job.

With a nearly 6% share in the company, Loeb commanded a lot of power, a huge asset if he remained happy with Mayer. But if he ever began to take issue with her strategies, he could make her job more difficult. Last fall Loeb told Mayer he planned to sell 20 million Yahoo shares, or a third of his stake, according to a January article in Vanity Fair. The article says Mayer countered, offering to buy twice that at $29.11 per share. The move was in keeping with Yahoo’s overall strategy of buying back company shares — so far Yahoo has repurchased $6 billion in stock. And with just 20 million shares left, Loeb’s ownership dropped below 2%. As part of the deal, he and his appointees resigned from the board, and Mayer bought herself some breathing room.

She also gets credit for articulating where Yahoo is going to invest. From the moment she arrived at Yahoo, Mayer signaled her desire to embrace the next generation of mobile computing. At the time the company was still handing out BlackBerrys. She brought iPhones — and iPhone engineers — to Yahoo and demanded that the company start making things for them. Mayer has grown Yahoo’s mobile audience 256%, to 430 million, during her tenure. In addition to mobile, the growth areas she sees are social, video, and “advertorials,” now known as native advertising.

But many of Mayer’s best-laid plans have soured. Shortly after she arrived at Yahoo, she hired a former colleague from Google, Henrique de Castro, as chief operating officer. De Castro had overseen the successful creation of Google’s display-ad business. At Yahoo he quickly reorganized the sales force to operate more like Google’s. As it turned out, the two businesses were very different, as were the companies’ cultures. De Castro continually rubbed advertisers the wrong way, or ignored them. Kellogg’s senior vice president of media, Jon Suarez-Davis, who currently enjoys a warm relationship with Yahoo, says he never even met de Castro. Meanwhile, inside Yahoo, de Castro alienated his peers, and colleagues picked up on escalating tensions between him and Mayer. One former employee says de Castro would tell his charges not to approach him without a “billion-dollar idea.” Another summarized his style this way: “He was always right, and you were always an idiot.” Whatever the reason, ad sales did not pick up under his leadership. In January, Mayer announced that he was leaving. It was a costly mistake; for his 15 months at Yahoo, de Castro made $58 million. De Castro did not return multiple requests for comment.

To her credit, Mayer acted fast to remedy the error. She vowed to spend more time with advertisers herself, a commitment she and her senior managers had already begun last fall. And she brought in Ned Brody, who had been head of AOL Networks (formerly Advertising.com), a digital platform for selling ads across AOL. A salesman who lives outside Washington, D.C., and works from Yahoo’s New York office, Brody believes Yahoo’s future is in the portfolio of ad products it is assembling. “The display-ad market will decline by 28% in the next five years. We have to build something broader,” he told Fortune in an interview. To that end, in January, Yahoo launched a new buying platform, Yahoo Ad Manager Plus, which makes it easier for ad buyers to spend money across Yahoo properties. Brody is also experimenting with launching a network that would allow Yahoo to serve ads on other sites, targeting users through the data the company collects in search.

One of Yahoo’s chief challenges is that it is locked into a 10-year search agreement with Microsoft that is not set to be renegotiated until next February. According to the terms of the deal, Microsoft’s Bing powers Yahoo’s search, while Yahoo supplies the sales force. Expecting early poor performance, Microsoft agreed to pay minimum guarantees through March 2014. But the deal has been disappointing. According to several people who have evaluated the deal for the company, Yahoo can’t get out of it.

To get around it, Yahoo has been investing heavily in developing tools for mobile search. In January it bought Aviate, which makes a technology for Android devices that can use personal data, the time of day, and other cues to present apps to you when you are most likely to be looking for them. Yahoo is betting that, even as consumers fret about privacy, they’ll increasingly want their smartphones to serve up information that is incredibly customized. Beyond this, reports surfaced in April that Mayer has her eye on dislodging Google as the embedded search engine on Apple devices. While ambitious, that might be nearly impossible. It would take a lot to persuade Apple to offer Microsoft’s search technology (through Yahoo) to its users.

A more troubling challenge is the technology that underpins the tools that marketers use to buy and place advertising on Yahoo and its affiliates. Yahoo Ad Manager Plus, a new buying platform, is still more difficult to use than what Yahoo competitors Google and Facebook offer. And Yahoo Ad Exchange, the company’s attempt to deliver a more computer-driven ad model, is built with the remnants of Right Media, an advertising exchange Yahoo purchased in 2007 that has long been the butt of ad buyers’ jokes. Adweek called Right Media “deeply flawed,” and ad buyers complain that it forces them to buy ad spaces they don’t want on Yahoo’s affiliate sites. This is happening at a time when marketers actually are craving such “programmatic” advertising, which provides buyers with more control over the audiences they target and gives them flexibility to spend more on the good stuff and avoid buying the bad stuff entirely. “They get an A- in terms of vision, but a B- in terms of execution,” says Mike Baker, CEO of software company DataXU, which Fortune 500 companies use to figure out ad purchases.

Which brings us to the final concern advertisers express: Yahoo lacks a top salesperson to explain its strategy to Mad Ave. Many people, including ad-agency executives and chief marketing officers, reinforce that this is particularly important as Yahoo makes broad changes to its product lineup, sometimes killing products, as it is reportedly doing with the video site Shine, and other times adding products that require a new conception. (Because Yahoo remains an important partner, no one would agree to be quoted.) For the moment, communicating with marketers has largely fallen to Brody. When asked about this concern, he demurred, saying, “If advertisers say that, then I’m not doing my job.” And he suggested that the perception of Yahoo’s advertising strategy today is weighed down by the legacy of what it was. Opinion, it turns out, is a hard thing to change.

Yahoo provided six advertisers to comment on their experiences with the company’s ad products. But when approached, the first three declined to speak. Kellogg’s Suarez-Davis confirms that the consumer packaged-goods company will increase the amount of money it spends with Yahoo in 2014, and credits Brody for advancing the relationship. Shannon Denton, CEO for North America at Razorfish, noticed a change roughly six to eight months ago and credits Brody, saying, “He understands the importance of data and measurement and also of integrating their formats. He went after those two things aggressively.” When asked, both agreed that the company’s lagging technology continues to be problematic.

Even if Mayer can fix her advertising tools and nurse her advertising relationships back to health, she will need to come up with a big opportunity to put the company on track for hypergrowth. She believes that native advertising holds that possibility, and in February she launched Yahoo Gemini, a self-service tool that pairs the company’s mobile search ads and its native-advertising units, which she calls Stream Ads. During the April 15 call, she said such ads are “on track to grow exponentially.”

Alibaba is like a mash-up of Amazon, eBay, PayPal — and Yahoo. The Hong Kong-based company sells goods to China’s 560-million-odd Internet users through a peer-to-peer marketplace as well as larger retailers, and it operates an online payments service. It also makes a bit of money off advertising, and according to Yahoo’s most recent quarterly earnings, Alibaba reported $1.4 billion in profits in the fourth quarter. (That’s more than Amazon and eBay combined.)

Mayer has said little about what she plans to do with the $16 billion (before taxes) Yahoo could reap when it sells part of its stake in the Chinese online juggernaut. She has intimated that the company may return a good deal of this payout to shareholders through continued stock buybacks, suggesting that Yahoo has the capital it currently needs to run its business.

There’s little doubt the IPO will be good for Yahoo. It’s possible that one reason Yahoo’s stock is worth less than the value of its three individual parts — the Alibaba investment, the Yahoo Japan stake, and the core advertising business — is that Alibaba’s valuation has been challenging to estimate. (The predicted range for the IPO is actually $136 billion to $245 billion, a gap more than three times the size of Yahoo’s entire business. What’s more, analysts may be factoring in the taxes Yahoo will probably have to pay on this bonanza.) Alibaba’s IPO will finally lend some clarity to Yahoo’s value. It could be that once the business has a definitive worth, the stock price will readjust itself. Mayer will retain a portion of the Asian assets, which could rise. Eric Jackson, a longtime Yahoo investor, has no plans to sell and believes the stock could go as high as $70 on the continued strength of the Yahoo Japan and Alibaba stakes that Yahoo will continue to own. “I’m not a Yahoo holder for the core,” he says.

There’s another possibility for the company after Alibaba’s IPO. The stock price could idle even as Alibaba’s value goes up. Investors could decide over time that the distinct businesses are more valuable on their own than they are together. In this scenario, Yahoo shrinks instead of grows, perhaps languishing in the land of legacy Internet companies like AOL. If the stock price drops, Yahoo could once again become a target for private equity investors.

Thus comes Mayer’s moment of reckoning. Neither outcome is all that bad for Yahoo, and Mayer’s legacy is guaranteed regardless. She will be the CEO who more than doubled the stock’s price after it idled well below $20 for years. But for Mayer, of course, there is only one model for success. In her most recent earnings call, she celebrated the company’s modest growth, and reminded investors she needed time. “We believe the hypergrowth we like to see will take multiple years,” she said. But while many may be rooting for her, that time will eventually run out.

This story is from the May 19, 2014 issue of Fortune.