(FORTUNE Magazine) – Newspapers should have been dead by now. They lost nearly 5.5 million subscribers between 1986 and 1996, and pundits declared the end was near. Young people didn't read, they said. The Net would replace paper. Corporate owners were destroying newspapers' souls. In 1993, Washington Post media critic Howard Kurtz wrote, "The smell of death permeates the newspaper business."

There's nothing like publishing your own obituary to get you going again. The newspaper industry has spent the past three years reinventing itself, and its efforts are starting to pay off. Last month the industry reported that in the six months ended in March, total circulation increased by 0.072%. This pathetic little number is symbolically huge: It is the industry's first sign of growth in ten--yes, ten--years. "All this business about online and so on is probably the best thing that ever happened to newspapers," declares Mark Willes, who, as chairman of Times Mirror, has seen the circulation of his six papers climb 4% since 1996. "When you're scared about whether or not you're going to survive, you start to do the things you need to do to survive."

Sure enough, many of those papers closest to the brink have come back nicely. The Chicago Sun-Times, which lost 30,000 subscribers in 1995, has since won back 6,000, bringing its total circulation to 494,000. That's still 5% below the paper's target penetration (518,000 readers), but it's a nice showing for a paper long thought dead. A couple of years ago people figured that Long Island Newsday was doomed to follow its sister publication, New York Newsday, to the newspaper junkyard. But in April, Newsday reported a 2.2% rise in circulation for the 12 months ended in March, its largest gain since 1987. In early May, at the annual meeting of Times Mirror, Newsday's parent, the mood was so upbeat that Willes hinted he may even revive the paper's New York City edition.

The secret to the industry's resurrection is simple: It got tough. Publishers realized that selling newspapers isn't much different from selling Coca-Cola or Crest. And relentless marketing has become standard practice: In Chicago, for example, the Sun-Times is going door to door to sign up new subscribers and has brought in 1,500 new orders a week since the effort began last year. Rather than assume customers will go out of their way to pick up a paper on the newsstands, Gannett Co. is trying to make USA Today's boxes as ubiquitous as Coke machines; the company now sells the paper in corporate cafeterias, university dining halls, hospitals, hotel lobbies, and in 1,100 Starbucks stores. USA Today's paid circulation is up to 1.79 million--second only to the Wall Street Journal's--and this year it's expected to generate operating income of $75 million on $533 million in revenues.

Signing on new readers is impressive, but keeping them is what counts. That means actually listening to your customers--an idea that in the newspaper industry is something of a novelty. Two years ago, when Raymond Jansen, publisher of Long Island Newsday, heard subscribers complain they weren't getting their papers early enough, he overhauled Newsday's production process so the paper would hit doorsteps by 6 A.M. instead of 7 A.M. Then he revamped the whole operation again to get the paper delivered by 5:30 A.M. Total cost: $12 million. And when the Arizona Republic recently discovered that some of its readers had neither the time nor the patience to wade through long features, its editors didn't resort to whining about America's dwindling attention span and the imposition of "lower standards"--they adapted: Long articles in the paper now include a summary box. Circulation is up 4.46% since last year.

Not even the venerable New York Times is above the fray. Last fall, the Gray Lady added color pages and pushed back its press deadline from 9:30 P.M. to 11:45 P.M. to fit in late-night sports scores. After years of declines, circulation is finally up--0.3%.

Still, the threat from the Internet looms. According to a survey done for MSNBC, 53% of the estimated 38 million Net users go online for news services. Online classified services such as The Monster Board and Career Mosaic threaten to chip away at newspapers' most profitable business, want ads. But here too, the industry is fighting back. In 1995, six major newspapers, including the New York Times and the Washington Post, launched Career Path, a Website that posts want ads from 70 papers nationwide. Already it's pulling in more than a million visitors a month. Even The Monster Board founder Jeffrey Taylor is impressed. "TV was going to crush radio, and that didn't happen," he says. "Now you see the same thing with newspapers [and the Internet]."

Wall Street has been even more impressed. Newspaper stocks as a group rose by 51.7%, compared with a 29.7% climb for the S&P 500 index. This year's first-quarter returns were up 7.4%. With good news all around, newspapers are already getting smug. Reminded of his industry's brush with death, Mark Hornung, vice president of circulation at the Chicago Sun-Times, scoffs, "As long as there are toilets, there'll be newspapers."

--Katrina Brooker