(FORTUNE Magazine) – Dick Parsons is not a man who should have a credibility problem. The chairman and CEO of Time Warner exudes a calm authority, whether he's talking about jazz or the latest technology for cable systems. Colleagues and competitors often liken him to a diplomat--"He's as good and as comfortable a statesman as there is in any business," says Comcast CEO Brian Roberts. He's also known as someone who keeps his promises. When he took over three years ago, the company, then known as AOL Time Warner, was reeling from the worst merger in business history. Since then Parsons has accomplished pretty much everything he said he would: He has slashed corporate debt nearly in half, stabilized AOL, and settled two federal investigations, and is set to buy a chunk of Adelphia's cable assets. Last year the company even posted a profit of $3.3 billion on revenues of $42 billion.

And yet Parsons has a major credibility issue on his hands. He's still struggling to convince investors that Time Warner (FORTUNE's parent) has put its considerable troubles behind it and is now poised to grow. Every move that was supposed to lift the cloud over Time Warner has been met by silence on Wall Street. It doesn't help that two of Time Warner's main businesses--cable and AOL--are out of favor on the Street. AOL's dial-up business is shrinking, and it is now trying to grab a big piece of the online advertising market by creating a free portal to compete with Yahoo and MSN. The cable business troubles investors who worry that competition from the phone companies and satellite operators--and possibly the Internet--will lead to a ruinous price war. On top of that, Time Warner still just plain confuses investors. Growth investors like the prospects of cable and AOL but find the publishing and broadcasting businesses a major drag--and would rather put their money in pure plays such as Comcast and Yahoo. Value investors, on the other hand, are spooked by the risks in cable and online. And though Time Warner owns some of the leading entertainment properties in the world, investors who believe content is king might prefer to own shares of Disney. Indeed, Time Warner trades at about nine times estimated 2005 earnings before interest, taxes, depreciation, and amortization (the measurement Wall Street likes to use for media companies); other diversified media companies trade at roughly 11 times expected 2005 Ebitda. In short: Time Warner stock has remained a stubborn underperformer at about $17 a share--almost exactly where it was a year ago.

It's a gorgeous May afternoon in New York City, and the Time Warner Center's tenth-floor cafeteria is bustling. With its soaring ceilings and wall-to-wall windows, the eatery offers some of the best views in the city. The prime real estate in the company's glitzy new skyscraper overlooking Central Park was originally to be used as a boardroom, but Parsons thought it would make a swell canteen. "We said, 'Oh, no, let's share this with the employees,''' he recalls. (Of course, from his luxurious 11th-floor office, Parsons gets to enjoy the same sweeping view all day.) As he dines, workers greet him with waves and smiles. CNN anchor Soledad O'Brien stops by to say hello. So does a fellow from the mailroom.

Over a heaping plate of cavatelli, the 57-year-old Parsons shows little overt anxiety about the stock price. He explains why he's more confident than ever that the company and the stock are moving in the right direction. In his first interview since he announced the Adelphia deal, Parsons laid out his plans for Time Warner's future. "You obviously can't run the company solely with an eye to the stock market," he says. "But, yes, getting the stock price up is a top priority of management."

Parsons says the company is likely to use some of its cash to pay a dividend or buy back shares; the stock would probably get a small bump from either move. He also predicts that the cable unit will continue to post strong results, which might give shares a further lift in the second half of the year. The biggest surprise: If AOL fails in its latest effort to capture more online ads through its free portal, which will offer an online search engine and features that previously had been available only to AOL subscribers, Parsons says he would consider spinning off the division as a separate stock. "If it works," he says, referring to the portal strategy, "this business looks like our publishing business, it looks like our TV business, it looks like our local cable advertising business." He has no timeline in mind, but says, "If this doesn't work, then you start to think about AOL much differently. You start to think about AOL in somewhat the same way I think about the cable company--we'd have access to the platform, but it would have its own currency to go out and do acquisitions or other deals. We'd have to find a way to maximize the value for our shareholders."

Not that Parsons or his lieutenants--Jeff Bewkes and Don Logan--are considering a full-fledged breakup like those other media companies are currently mulling. Time Warner would retain a controlling stake in the cable and probably in any AOL spinoff too. "We're not trying to figure out the flavor of the day," insists Logan, the blunt former Time Inc. CEO who now serves as chairman of the corporation's communications group. "Look at Viacom: Now they're going to break it in two. What the hell for? I can't figure it out. Can you?"

Instead, Time Warner executives--including Parsons, Logan, and Bewkes, who chairs the entertainment group--insist that these businesses are better together than apart. AOL supposedly helps all the units better understand the Internet, for example, and the movie studios benefit from having access to networks that buy their content. In turn, knowing the going rate for, say, reruns of the Warner Bros. show Friends helps Turner Broadcasting negotiate prices with other studios whose shows TBS might want for its comedy lineup. "It gives you real market information," Bewkes says. "Is the benefit 50% more earnings? No, but it doesn't need to be more than 10% or 15% to be a real advantage."

Turner, meanwhile, is about to benefit from Time Warner's recent deal with Comcast to acquire Adelphia's cable properties: Its networks will have access to another three million or so cable viewers. The deal calls for Time Warner to create a separate cable stock that would have its own equity. (The spinoff will be 84% owned by Time Warner, and it will carry its own debt, but all its revenue--and losses or profits--will fall on the Time Warner earnings statement.) The spinoff also gives the cable business room to buy another cable company or strike alliances with, say, a wireless operator, without further confusing Time Warner shareholders.

Parsons thinks investors will come around on cable's prospects. He acknowledges that the phone companies are a threat but claims their video networks are years away. In the meantime, Time Warner Cable keeps stealing customers from the Baby Bells. The company's digital phone service, which runs over upgraded cable lines, now has more than 500,000 subscribers, and Parsons predicts that Time Warner will serve more than a million phone customers by the end of the year.

Investors were worried Time Warner would overpay for Adelphia, forcing it to heap on debt. But by using stock in the new cable company to help pay for the assets, Time Warner ends up forking over only about $11 billion in cash ($9 billion for the Adelphia assets and $2 billion to Comcast to unwind an old joint venture). That's no small amount, but Parsons says Time Warner has enough money to buy Adelphia, reinvest in the businesses, and still contemplate a buyback or a dividend. (That's largely because the company has done a respectable job lately of converting operating income into free cash flow--last year the company posted $3.3 billion in free cash.)

The spinoff may also make Time Warner shares more desirable to the anticable crowd. "If you have to play media, I would want to be long content and short distribution," says famed short-seller Jim Chanos, founder of Kynikos Associates, who doesn't have a position in Time Warner. "In Time Warner's case, I would wait until they spin off cable, and then I would be long the parent company and short the requisite amount of Time Warner Cable to hedge out the cable exposure."

America Online CEO Jon Miller is standing on the balcony of his office--Steve Case's old digs--in Dulles, Va., showing off the sprawling campus. He points to a huge building filled with AOL programmers and a bustling day-care center. It is a reminder of just how big AOL remains. "I still have people come up to me and ask, 'Do you guys make any money?'" Miller says, shaking his head. Last year AOL posted $934 million in operating income and contributed about $1 billion in cash flow to Time Warner.

Miller's job is to keep the cash flowing even as AOL loses subscribers. His plan is simple: Build an online portal business that offers consumers free online search, music, lots of AOL's premium content, and web-based e-mail--all with an eye to attracting online advertisers.

Test versions of the AOL.com site, which will launch later this year, look promising: True to AOL's heritage, it is easy to navigate and boasts some consumer-friendly features such as a pull-down bar on the browser that contains little images (not just web addresses) of the sites you've just visited. Almost all AOL content, including news and information--and even goodies such as a hit online concert series--will be available free.

But one can't help getting the impression that AOL's strategies are a little stale. Indeed, it seems to be reinventing itself in the image of a more successful and more highly valued company--Yahoo. AOL's big plan for retaining subscribers--partnering with cable companies--feels a lot like Yahoo's alliance with telcos SBC and Verizon. (The only company AOL has announced a deal with is its sister Time Warner Cable.) Similarly, the plan to capture online ad dollars, the hottest area of advertising right now--shouldn't AOL have been on that years ago?

Miller insists the answers weren't so obvious when he arrived at AOL in the summer of 2002. One respected Silicon Valley executive advised him to focus entirely on the subscriber business. And AOL had almost no credibility with advertisers anyway. Back in the old days the company was hard to work with, and it didn't even have a way to accept ads created in HTML, the standard language of the web. "If I had stood up day one and said, 'Let's make this big bet on advertising and forget about everything else,' I don't think you'd be talking to me today," Miller says.

Advertisers, hungry for alternatives to MSN and Yahoo, seem willing to forgive AOL's past transgressions. In the first quarter the company posted $311 million in ad revenue, up 45% from a year earlier. "I think you've got an industry that is waiting or hoping for AOL to rebound," says Jeff Lanctot, vice president of media for Avenue A/Razorfish, which buys online advertising for big clients.

That should mean good things for Time Warner shareholders. Today investors value AOL more like EarthLink or United Online, much smaller companies that focus on providing Internet access. Most analysts think Time Warner is trading as though AOL were worth about $8 billion, or less than $2 a share. But suppose investors applied a higher multiple to AOL's advertising earnings--nothing like Yahoo's multiple of 30 times Ebitda--but maybe something close to 20 times Ebitda. Based on that math, AOL could be worth closer to $18 billion, or an extra $2.20 a share.

Even with so much at stake, Miller insists he's not feeling extra pressure to perform. "Dick has been very clear: The deal is, you do what you say, and if you do that, you're cool."

If there's a knock on Dick Parsons it's that he doesn't have a grand vision for Time Warner. This lack of vision is partly by design. His predecessors, after all, had plenty of visions for the combination of AOL and Time Warner (remember Steve Case and Jerry Levin's promise that it would become the most valuable company in the world?), none of which panned out. During lunch I ask Parsons what his grand plan is. "It's not terribly different from what you see today," he says. He might as well be reading from a script: "We aspire to be the best diversified media company in the world, to create and package the best content, and to deliver it in more ways to more people than any other company. But," he adds, sounding more candid, "we're not going to be some newfangled thing that people can't understand."

No one would argue with that logic. "I think Time Warner has had enough sizzle to last a lifetime," says media banker Steven Rattner of Quadrangle Group, which doesn't have a stake in Time Warner. "I don't think sizzle is what they need at the moment. They need steady hands on the tiller, and that's what they seem to have." To understand Parsons' view of the world, remember the situation he inherited just three years ago. Time Warner was a mess, but few outside Parsons' inner circle fully appreciate just how bad things got. One senior executive remembers receiving a call from Parsons in the summer of 2002. The stock was trading at around $8 a share, the credit agencies were ready to downgrade Time Warner debt, the SEC had begun looking into accounting irregularities at AOL, and Parsons needed to untangle one of Time Warner's relationships with Comcast. But Comcast was reluctant to convert its joint-venture stake into a piece of Time Warner, given its low valuation. "The wheels are coming off this company," Parsons told the executive, who didn't want his name used. He adds, "It was the only time I've ever seen Dick rattled."

Parsons persuaded Comcast to accept a combination of cash, Time Warner stock, and a stake in the cable division, and the companies announced a restructuring of their partnership in August 2002. "I think Dick has been the perfect person to lead Time Warner through a difficult period," says Comcast's Roberts. "Time Warner needed a leader with maturity and integrity, both of which are embodied in Dick Parsons."

Parsons' detachment may also reflect the way he came up in the business. He's not an entrepreneur like Ted Turner or Rupert Murdoch, and he lacks a founder's fervor. A lawyer who worked for Nelson Rockefeller for many years, he became president of Dime Bancorp in 1988. While running Dime, he joined the Time Warner board, and in 1994, Jerry Levin asked Parsons to become the company's president.

Unlike a prior generation of media moguls, Parsons isn't consumed with work or his company, or at least that's the image he cultivates. He's an avid jazz fan--he says he hardly listens to any pop music. His taste in reading is varied: He says he recently finished the New York City history Island at the Center of the World and the novel Kite Runner. Currently he's working through two nonfiction works: The Complete Game Theory and DisneyWar--he says he's "halfway through DisneyWar, which I find depressing, so I can't just plow right through it."

If Parsons has a professional passion, it appears to be, of all things, HR. "The longest meeting I have with Dick Parsons is when we sit down once a year and talk about human resources," says Turner chief Phil Kent. It may not seem like the best use of a CEO's time, but it turns out to be a very big deal. All those synergies? Well, you don't get them if the units don't play well with one another. Parsons may achieve what his predecessors failed to do: dismantle Time Warner's fiefdoms. Division heads say they're now encouraged to work together, and they often do so in ways that give them advantages over the competition. Turner's Kent, for example, can spend countless hours with Time Warner Cable, understanding how new products such as video-on-demand are going to change his business. Kent's rivals at Viacom don't get the same access.

But what does all that harmony mean for investors? There's no formula for factoring it into the stock price, but Merrill Lynch analyst Jessica Reif Cohen (who has a $24 price target on the stock) thinks the new spirit of cooperation could translate into the development of new businesses--something Time Warner has never excelled at. "I can't understand how they had AOL and they didn't create [online] search, or how they had Warner Music and AOL and didn't create something like iTunes [the Apple online music service]," she says. "They are now empowered to create new businesses that take advantage of the assets they have."

At the very least, the company may avoid bad calls such as Levin's decision to merge Time Warner with AOL. These days, big deals are scrutinized by Bewkes and Logan--the most vocal critics of the AOL merger--and the two aren't shy about poking holes. Logan, for example, initially hated the idea of bidding for MGM. "What do we need more movies for?" Logan recalls asking. "I became a convert. At the price we were talking about, it would have been a very good deal." But Time Warner wasn't going to do the deal at just any price: When the valuations soared, the company walked away.

Parsons may not be frustrated with the stock price, but Bewkes and Logan certainly are. "Don and Jeff have come from parts of the company that built great businesses, but they were one step removed from managing the stock," Parsons says, sounding characteristically nonchalant. "I've had nothing but exposure to the stock. Our stock floats on a big ocean out there called the bigger market."

However, investors are growing impatient, and for all Parsons' success at Time Warner, his tenure will be judged on whether he has improved his shareholders' lot. Some investors may be comforted by a steady hand today, but if these latest moves--dividend or buyback, cable spinoff, AOL's ad gambit--don't pay off, they may instead start looking for someone to shake things up.

As we get ready to gather up our lunch trays, I suggest to Parsons that he sounds more confident and relaxed than he has at any point in his tenure as CEO. He quickly volunteers that he is not more relaxed but says he's feeling optimistic about the company. "If you ask anyone with any sense who has the best collection of media assets, it's Time Warner, and Murdoch comes in a solid second," Parsons says. "Who has the best management, stem to stern? We do. So how bad can it go?"

FEEDBACK smehta@fortunemail.com