(FORTUNE Magazine) – IF MARTHA Stewart's troubles have dimmed her self-confidence, you'd never know it from talking with her. When she was offered a starring role in The Apprentice, she tells me one afternoon, "I thought I was replacing The Donald. It was even discussed that I would be firing The Donald on the first show." It's a cold, damp October day, and Stewart is holding forth in her tidy, glass-walled office on the 24th floor of her company's Midtown Manhattan headquarters. Her prime-time NBC TV show, The Apprentice: Martha Stewart, has launched with lackluster ratings, but the blame, as she sees it, lies not with her performance or her personal brand being a tad overexposed but with the overexposure of The Apprentice itself. Not until shortly before she "got home," she says--from a five-month federal prison stay--did she learn that Trump's show would remain on the air too. And when did Trump learn that she intended to bump him off his own show? "I don't think he ever knew," she says.

Stewart betrays no disappointment in her show's numbers. In fact, she describes it as a triumph. "We're getting six to seven million viewers a night," she says. "Guess what? That's damn good. People walk away from the show thinking, 'What a nice company that is,' and 'Boy, do they do good things.'" Would a runaway hit have been better? Of course. But in her view, she is getting prime-time product placement--the product, of course, is Martha--just when she needs it most. Her face is on billboards and buses across the country. It's a tremendous promotional platform, more valuable than millions in ad dollars could buy.

And so the redemption of Martha Stewart--media mogul, multimedia superstar--continues. Maybe you loathe her. Maybe you love her. Either way, it's hard not to be amazed by her dramatic reversal of fortune. A year ago she was incarcerated at Alderson Federal Prison Camp in the hills of West Virginia, for lying to government investigators about a suspicious stock trade. "I was in the wrong place at the wrong time," Stewart says. "I fell in a hole." Today, at 64, she is ubiquitous. Her flagship magazine, Martha Stewart Living, has seen ad pages jump 48%; her new advice book, The Martha Rules, is on the New York Times bestseller list. She's landed a syndicated daytime TV show, a $30 million satellite radio deal with Sirius, a DVD deal with Warner Home Video, a music deal with Sony BMG, even a partnership with KB Home to build Martha Stewart--branded residential communities. After plunging from a peak of $295.6 million in 2001 to $187.4 million last year, revenues at her company, Martha Stewart Living Omnimedia (MSLO), are rebounding to an expected $208 million this year; after the company's seven consecutive quarters of losses, Wall Street projects a return to profitability in 2006.

None of it happened by chance. As I learned in the course of a year's reporting and multiple interviews with Stewart, she plotted this comeback with her signature painstaking precision--practically from the day she was convicted. While she benefited from America's well-known fascination with celebrity resuscitations, her return may be the strongest evidence yet of her strategic sense and business acumen. Stewart has installed first-rate management at MSLO: CEO Susan Lyne, the former top programmer at ABC, and chairman Charles Koppelman, the onetime boss of EMI Records North America. (Don't let his role as Stewart's smiling, cigar-chomping sidekick on The Apprentice fool you; he's a power in the company.) Stewart's operatic fall and thunderous return speak volumes about the resiliency of this entrepreneur who was America's first self-made female billionaire. She's No. 21 on our 2005 Most Powerful Women list, and she earned it the hard way.

Make no mistake: Serious risks persist for Stewart and her company. She is a convicted felon and, her ongoing appeal and protestations of victimhood notwithstanding, was put away by a jury of four men and eight women who voted guilty on four counts. A Securities and Exchange Commission insider-trading investigation is pending. With her history of going from darling to devil to darling in the public eye, the mood could turn against her once more--and may already be souring. Her company's stock, which doubled during her prison stay, is down 47% since her release in March, reducing the value of Stewart's personal holdings from $1 billion to just over $500 million. Press accounts, once brutal and then ebullient, have turned chilly again. Is she overexposed? Perhaps, but she knows only one way to operate: full speed ahead. She never had a plan B for her comeback. And arguably, she doesn't need one. "I have learned," Stewart says, "that I really cannot be destroyed."

In July 2004 I met Martha Stewart for dinner at Rebecca's, one of her favorite restaurants in Greenwich, Conn. It was just three days after she had been sentenced to five months in prison plus five months of house arrest--a fate she'd hoped to avoid even after her conviction. Advertisers were fleeing her flagship magazine, revenues were tanking companywide, profits were gone, and MSLO stock was trading at $11 a share. (Four years earlier it had been as high as $34). She'd been ridiculed on the front page of the New York Post two days before in a cut-and-paste picture of her in prison stripes.

Given all that, Stewart was remarkably composed, dining on grilled tuna, enjoying a glass of white wine. "My daughter told me that all this makes me more interesting," she joked. "Great, if only I didn't have to go through it." She was struggling with whether to go to prison then or hold out through the legal appeal process. She called it "my conundrum." When I asked, perhaps foolishly, if she was at all curious about or intrigued by the idea of going to jail, her reply was classic Martha, tough and no-nonsense, delivered with a touch of hauteur: "Curious?! Intrigued?! No!"

Yet the wheels were already in motion for her comeback--and serving time would play a key role. The plan had been launched just days after her conviction, in early March, when Stewart's good friend Jane Heller, who is also her private banker at Bank of America, arranged for her to meet with Koppelman. Once a major player in the music business--he worked with Sinatra and Streisand, signed Billy Joel, and ran EMI Records North America for three years--Koppelman, now 65, had become a sort of freelance advisor to bigwigs in crisis. That he was helping Michael Jackson with his financial problems and chairing shoe company Steve Madden while its founder was in jail for stock fraud and money laundering didn't put Stewart off. It intrigued her. "He had the kind of experience I needed," she says.

On Saturday, March 13, at Koppelman's home on New York's Long Island, he and Stewart spent several hours together with Heller and her husband, Steve Gerard (CEO of publicly held CBIZ Inc.). During the first hour Stewart kept talking about her trial and what she viewed as a bad deal at every level--overreaching prosecutors, an unfair jury, her failed defense. Koppelman listened, then stressed practicality: "Take control of what you can control--your business."

It was just what Stewart needed to hear. The previous June, after being indicted, she had stepped aside as chairman and CEO of MSLO. Her No. 2, Sharon Patrick, took over as chief, and the company took steps to distance itself from its founder--"de-Martha-ize" it, as some insiders said. Stewart's name was downsized on the cover of Martha Stewart Living and her presence diminished inside its pages. (Disclosure: Time Inc., FORTUNE's publisher, owned Martha Stewart Living until 1997, when it sold the magazine to Stewart, citing the risks inherent in a single-personality publication.) Some of MSLO's outside directors even considered changing the name of the company.

Stewart hated the strategy. "It was all about placating the lawyers and Wall Street and advertisers," Stewart says today. She says she told Patrick and others, "If it's a brand name, you don't remove it or minimize it. It's a bad idea." That Saturday at Koppelman's house she decided it was time to reassert her control. She owned 30 million MSLO shares, some 60% of the stock, and more than 90% of the voting shares. She and Koppelman talked about using her leverage to reconstruct the MSLO board. Her visit, in fact, turned into a recruiting effort; after lunch she asked Koppelman if he would sign on as a director. He agreed, with one proviso. "I told Martha that I would consider it if she understood one thing," he recalls. "There would be circumstances when what's good for Martha Stewart isn't good for her company. But what's good for her company is 100% certainly good for Martha Stewart."

Stewart was only warming up. In June she added to the board Susan Lyne, who as president of ABC Entertainment from 2002 to 2004 had championed such future hits as Desperate Housewives and Lost. Unbeknownst to Lyne, she was already in Stewart's mind as a potential replacement for Patrick as CEO. Stewart also set out to guarantee herself some added financial security. She asked the newly reconstituted board to renegotiate her employment contract, slated to expire that October. With Koppelman carrying water for her, she got her wish: the same pay--$900,000 annual salary plus a bonus of up to 150% of the base--and the same perks (such as a car and driver), through September 2009. The board would withhold her pay during any prison stay. It also reduced her location rental fee--what MSLO pays to use her homes in magazine shoots and TV demos--from $2.5 million annually to a maximum of $750,000 annually. But MSLO agreed to pay her $200,000 upfront for her television and radio appearances, plus a minimum of $500,000 to do The Apprentice.

Mark Burnett, the reality-TV guru behind Survivor and Trump's Apprentice, had called on Stewart in May, offering what he now calls "a life raft of hope": a prime-time TV opportunity. (Says Stewart: "I didn't look at it as a life raft.") Burnett, who wanted to extend the Apprentice franchise and use a woman host, wasn't being altruistic; he smelled good television. Stewart was, as he puts it, "the most charismatic and famous woman," and her legal downfall made her all the more compelling as a reality-show character. "Donald was down too. These are winners who deal with the shit things in life. These people are inspiring," he says.

Burnett took his idea to Jeff Zucker, the president of NBC Universal Television Group, who recalls wondering, "Would America embrace her?" But, he says, "America loves a great comeback story. We didn't do any research. These are gut decisions." By early summer Zucker agreed to a Martha Apprentice, and later he also agreed to carry a daytime TV show for Stewart, whose long-running domestic-diva program had been dropped by CBS.

As these pieces fell into place, Stewart turned her attention to her legal conundrum. "There wasn't one lawyer who worked on my case who advised me to go to prison," she says. "They said it would look bad. It would harm my case. It would tell people that I was guilty." But Stewart insists she knew all along what she had to do: serve the time, get it over with, so she and her company could move on. "My life is my business. My business is my life. I've said that a thousand times. I had to do it because I knew it would change things--jigger a change--in the company."

In mid-September, when Stewart held a press conference to announce that she would begin her incarceration as soon as possible, she seemed, well, liberated by the decision. And a month later, when she moved into the minimum-security West Virginia facility that over the years has housed Billie Holiday and "Squeaky" Fromme, her recovery scheme continued in her absence. MSLO's new board set its sights on CEO Patrick--who had worked with Stewart for 11 years--and pushed her out. "When I resigned and Sharon took over," says Stewart now, "it was clear that the job was way too much for one person." She had urged Patrick, who was criticized by investors as disorganized, to hire a No. 2. Patrick resisted. ("A COO couldn't solve MSLO's biggest problems--loss of ad revenue and uncertainty," Patrick now says.) "She said she could handle it," Stewart says, shrugging. "She just wasn't handling it."

Stewart--or even Mark Burnett--could not have scripted what happened next any better. The MSLO board chose Lyne, 55, to take over as CEO just as Desperate Housewives, the show she had developed at ABC before Disney replaced her, was emerging as TV's biggest new hit. Six days later Kmart, which sells $1 billion a year in Martha Stewart--branded items, announced its merger with Sears, prompting widespread speculation that Stewart's retailing deal would be extended to Sears as well. MSLO's stock rose 27% in three weeks. Prisoner No. 55170-054 in the hills of West Virginia saw her net worth increase by $148 million.

Three weeks after Stewart got out of jail--or "Yale" as she preferred to call it ("I always wanted to go to Yale," says the Barnard grad)--I met with her at her Bedford, N.Y., farmhouse. It was the Monday after Easter. Stewart, dressed in casual orange pants and gold clogs, seemed as restless as ever. "I want to take you down to see my stables," she said, and hurriedly showed off her Friesian horses. She was permitted out of her house only 48 hours a week and exclusively for business, grocery shopping, medical, or religious purposes; the day before she had gone to church on horseback, a rarely permitted riding opportunity.

Her three-bedroom home, in the process of being renovated, was almost empty of furniture. But the kitchen--completed, she said, just hours before her return from Alderson--was magnificent. She whipped up cappuccinos there, and then we settled down at her galvanized-tin-topped dining room table. (She designed it herself.) Over her half-year of house arrest she would host 1,700 people for meals at that table: advertisers, business partners, and potential co-conspirators in her comeback. She even hired a famous chef, Pierre Schaedelin, away from Manhattan's swank Le Cirque to cook for her constant stream of guests.

Stewart would come to resent her house arrest (especially when the probation department extended it by three weeks), in some ways even more than her prison stay. At Alderson, an all-female facility that houses about 1,100 prisoners, "I got relaxed," she confides. The strain of her legal battles and the constant media pressure were lifted. "I felt calmer. I felt better," she says. "My stress level, I'm sure, was cut in half." When Stewart was denied a job in the prison kitchen--assigned instead to clean the warden's headquarters--she coped. "I did the vacuuming and the cleaning of the machines--I'm good at that," she says. She worked every weekday from 7:30 A.M. to 3:30 P.M., for 12 cents an hour. "When the envelope-opening machine in the post office broke, I was the only one who could fix it," she recalls proudly.

The prison food--heavy on carbs and "bad meat"--was terrible. "It would have been great to tell them that I'm a vegetarian," she says, though she's not. "I sign up for vegetarian meals when I fly." She lost 20 pounds, skipping dinner in the cafeteria and learning how to microwave meals with fellow inmates. ("Simple pastas, kale quesadillas, dandelion greens, and vegetable mélange made from whatever was left in the sad garden," she says.) She worked out in the prison gym for an hour each morning; she practiced yoga each night, and taught yoga classes as well.

The worst thing was being cut off from her business. She had no Internet access. She was not allowed to conduct business with visitors or by telephone. Limited to 300 minutes of phone time per month, she says, "I told the warden, 'I use that in a day!' He told me, 'You have to make an adjustment.'" She wrote an introduction for Mark Burnett's book Jump In! and used a "precious 15 minutes," she says, to read it to her assistant over the phone. The next day she got summoned to the captain's office. "He said, 'This is business.' I told him, 'I beg to differ. This is one friend doing another friend a favor. You can't look at this as business. I didn't get paid for it.'"

Lyne and Koppelman visited her a half-dozen times. They were permitted to tell Stewart what was going on at her company, though she wasn't allowed to make decisions. But her mind kept working. "Oprah was on every day," she recalls. "I was impressed by how well-produced it was. I paid attention to the technical stuff so I could apply it to my own show." She also thought about food as a business, she says: "Martha Stewart foods and other retail initiatives." And she began outlining her book, The Martha Rules, which was inspired by a seminar she did for fellow prisoners on entrepreneurship.

As for her post-prison PR challenges, she says, "there were other people who were figuring out how to change the image of Martha the evil horror that was presented by the press." In February, Lyne hired former Texas Governor Ann Richards as a media advisor and had her consulting firm, Public Strategies, survey 1,200 women across the country. The results of this brand study, the most extensive MSLO had ever done, were encouraging: 50 million American women--half the female population--call themselves "supporters" of Stewart, estimated Public Strategies. Stewart's "unfavorable" rating, at 27% then and 21% by May, was hardly terrible for a public figure. (Hillary Clinton's is 33%, according to Public Strategies.) Lyne says the research confirmed what she believed: "The Martha Stewart brand and Martha herself are our most valuable assets."

By the time Stewart was released, in March, she was ready to run, with the study providing a roadmap. Her longtime PR counsel, Susan Magrino, fielded some 500 interview requests, but the Martha remake team decided to avoid putting her in front of Barbara Walters, Larry King, or others who might focus on prison or her trial. Instead they put together a video of Stewart in her beautiful Bedford kitchen with her mother and daughter, then fed the tape to TV outlets, which played it willingly. "That stopped the photographers from hanging out of the trees," Lyne says. The cleverly crafted footage also enabled MSLO to play up the idea that Stewart was reconnecting with her family--precisely what the Public Strategies research indicated her supporters wanted to see.

Meanwhile Koppelman--who stepped up to chairman of MSLO in June--began creating new ventures to capitalize on Stewart's notoriety. He got Warner Home Video to produce Martha Stewart how-to DVDs using 1,600 hours of backlogged TV shows. He cut a deal with Sony BMG for a series of Martha-branded holiday and home-entertaining music CDs. He hooked up with Mel Karmazin at Sirius and spawned Martha Stewart Living Radio, a 24-hour-a-day satellite channel. "She'll enable us to make a lot of money," says Karmazin.

At Koppelman's urging, Stewart even flew to North Carolina in late July, during her home confinement, to meet the CEO of KB Home, Bruce Karatz, and tour one of his developments. Karatz says that her felony conviction didn't faze him: "I felt sorry for her in a lot of ways. She paid heavily for what she did. A lot of people would shrink from public view. She didn't." Zipping through model homes that day, Karatz recalls, it was Stewart--not Koppelman or Lyne or the other MSLO folks there for the tour--who was taking pictures and making notes. "She's the one doing the work. I love that," he says. She too was surprised at the house tour: "You get unbelievable quality and space for the price," Stewart says. "My garage costs more than a 2,500-square-foot home!"

A deal quickly followed. Starting in Cary, N.C., KB plans to build 650 Martha-branded houses in the $200,000 to $450,000 price range--upper-middle-class renditions of Stewart's homes in Bedford and East Hampton, N.Y., and Seal Harbor, Maine. (Notably absent: Turkey Hill, her famous Westport, Conn., abode, which she says she plans to sell: "I hardly ever go there anymore. I don't miss it.")

The comeback accelerated. She was cheered by national magazine editors at their annual awards show in the spring, and her house-arrest ankle-bracelet became a titillating topic for talk-show hosts. Business improved too. Revenues at MSLO's largest division, publishing, rose 24% in the third quarter. Even the two-year-old magazine Everyday Food (which, thanks to Stewart's prison stint, has added microwave recipes) showed a 21% increase in ad pages. Koppelman's various new ventures promised future revenue without major capital outlays. The Sirius deal went one further, delivering a $7.5 million annual fee for four years. As for The Apprentice: Martha Stewart, "we've had incredibly high demand [among advertisers]--it's our most in-demand show," NBC's Zucker told me one week before the Sept. 21 premiere. Anticipation had reached a fever pitch.

"Two hours! It took me two hours from Bedford!" exclaims Stewart, storming in late on a mid-September day to lead a tour of MSLO's creative offices, across town from the corporate HQ. As she dashes into a vast airy corner of the 150,000-square-foot expanse, she explains that this area contained ordinary offices a year ago. While she was in prison, it became the TV set and contestant living quarters for The Apprentice. After filming wrapped in June, it was transformed again, into a showroom for Martha Stewart Signature furniture. Nearby, producers splice promo spots for her new daytime show. A few doors down, a team bats around ideas for her radio channel.

Stewart scoots through a gleaming test kitchen, grabbing a pear for lunch on the fly. She seems almost giddy as she talks about her revived relevance inside her company. "I've dined with more advertisers in the last six months than in the last four or five years," she says. She is not burdened with running MSLO day-to-day; her title is simply Founder. "I'm not even approving decisions," she says. "Rather, I'm giving my blessing."

But in the weeks that followed, her comeback bloom began to wilt. Martha, her daytime program, delivered ratings 20% below expectations. That means MSLO, which owns the show, will have to compensate advertisers with free ads in the coming months. The Apprentice, meanwhile, registered only six million to seven million viewers in its first installments, about half the audience Trump garnered a year earlier. Critics began saying that MSLO had overextended the Martha brand--and investors reacted. The company's shares plummeted from $33 in mid-September to $20 a month later. When MSLO reported another quarterly loss in late October and Lyne indicated that the next quarter would be weaker than Wall Street expected, the stock dipped to $18.

Within the Martha universe, the people in charge appear to take all this in stride. About The Apprentice, CEO Lyne says, "It's not a smash hit, but the ratings are improving." In her old job as TV programmer, Lyne might have pushed for the soft Martha Stewart of The Apprentice to add some edge to draw a larger audience; as CEO of MSLO, sacrificing brand image for ratings is the last thing she would allow. And since neither MSLO nor Stewart herself owns a piece of the program, low ratings are more NBC's problem than theirs.

In this light, MSLO's unusual business arrangement with Apprentice producer Mark Burnett might be seen as an insurance policy of sorts. In lieu of a big cash payment (which MSLO couldn't afford at the time), Burnett received a warrant package that, at MSLO's recent stock price, is worth $13.5 million to him. That gives him a significant financial incentive to safeguard the Martha brand, even if it conflicts with drawing viewers to NBC. "A lot of people look askance at the warrant," admits Lyne, whose predecessor, Patrick, negotiated the arrangement, "but I would have a hard time arguing against that deal. Mark is a true partner." Burnett agrees: "I'm incented to make sure MSLO is properly represented," he says. How does the network feel about the deal? "There's zero tension with NBC on this," says Burnett. NBC's Zucker concurs.

In many ways, the attention paid to The Apprentice is a sidelight to a bigger business challenge facing Stewart and her company: MSLO's partnership with Kmart. Sales of Martha merchandise at the chain nets MSLO more than $50 million a year under the current contract; after the Kmart-Sears merger investors bet that the deal would expand. Yet no such broadening has occurred, and prospects seem in doubt. "We have a plan that doesn't include Martha Stewart in Sears," says Eddie Lampert, the investor who controls both Kmart and Sears. MSLO's historic arrangements with Kmart have been extremely lucrative for Martha. In the future, says Lampert, "we want a two-way relationship." Indeed, when he extended MSLO's Kmart contract last year through 2008 and 2009, he set new terms for the added years that will reduce by some 60% the minimum royalties MSLO receives--bound to hit MSLO's bottom line.

Stewart says she's "chomping at the bit. We have millions of ideas for Sears." Since she returned from prison, she has met with Lampert a half-dozen times. She thinks he's "brilliant." He says about her: "She's been incredibly gracious and charming"--but to him, of course, this is business, pure and simple. Asked whether Martha merchandise will be in Sears next year, Lampert says, "It's more a question for them than for us." Talks continue. "Will it work out? I don't know yet," Stewart says, throwing up her hands.

While MSLO investors hope for the best with Sears, they should feel confident that the company finally has a management team that works. Stewart and Lyne are, by all accounts, getting along well. Lyne has experience reporting to larger-than-life personalities, such as Rupert Murdoch and Michael Eisner, and knows how to be both commanding and unthreatening--a tricky balance that is crucial for anyone who works with Martha. Stewart says that her "saddest day" in the past few years was when she gave up her job as chairman and CEO of MSLO. That doesn't necessarily mean she's angling to retake her CEO post: "I'm really happy with Susan Lyne as my CEO, okay?"

"What I don't want," Stewart says, "is to be told that I can't be a corporate officer." Neither the government nor the New York Stock Exchange, where MSLO trades, prohibits convicted felons from being officers or directors. The SEC, however, has an outstanding civil action against Stewart for insider trading, and it could ask for that sort of prohibition in settlement talks. "I should not have resigned," Stewart says. "No, I really feel that I shouldn't have. I didn't have to, but I did it mostly for perception--to show that I was taking my situation seriously."

So what does Martha want? She suggests that she would like to be MSLO's chairman at some point again. When I share that news with her current chairman, Koppelman, he seems quite surprised. "Why would she want to do that?" he asks. "She's got a better gig now. She's Martha Stewart!"

REPORTER ASSOCIATE Eugenia Levenson

FEEDBACK psellers@fortunemail.com