(FORTUNE Magazine) – In an age of ugly symbols, a handful of companies have come to serve as shorthand for what's wrong with corporate America. In 2004, Halliburton moved to the top of the roster.

Mention its name and images flash: Vice President Dick Cheney bestowing fat, no-bid contracts on the company he once ran; a giant corporation engaged in shameless war profiteering--charging outrageous prices to provide fuel for Iraqis and meals for American troops. Halliburton became a punch line, as when Tonight Show host Jay Leno noted that Saddam Hussein was captured with $750,000 in cash on him. "They think," Leno explained, "that he was trying to buy three gallons of gas from Halliburton."

With the election long over, the media typhoon has moved on. Halliburton's Houston headquarters, which fielded 200 media inquiries a day during the campaign, now averages just three. And as a result, another Halliburton story has been ignored: Halliburton's business.

This is a very different story, though it's also not a pretty one. The truth is that the conspiracy theories about the Vice President's involvement in Halliburton's Iraq contracts are either unproven or flat-out wrong. And while the company's Middle East operation is the subject of scathing audits and investigations, it's hardly raking in scandalous profits. Indeed, Kellogg Brown & Root (KBR), the part of Halliburton's business that America learned to hate because it was making far too much, is the part of the business Wall Street hates because it is making far too little.

The trouble with Halliburton goes way beyond its misadventure in Iraq, which is just the most visible example in a string of self-inflicted fiascos. Federal prosecutors are now investigating how the company sidestepped U.S. sanctions against doing business with Iran as well as a former KBR chairman's alleged involvement in a Nigerian bribery scandal and possible bid-rigging overseas. There was an ugly encounter with the SEC dating back to 1998, focusing on the failure to disclose an accounting change that allowed the company to hit its quarterly earnings targets; Halliburton settled the case last year after paying a $7.5 million penalty, reflecting the SEC's view that "unacceptable lapses" in Halliburton's cooperation had delayed the investigation. Then there's the company's attempt to cut off promised health benefits for 4,000 retirees--which a federal judge has now blocked.

But as you'll see, three debacles loom largest of all: the work in Iraq; a $2.5 billion construction project off the coast of Brazil; and Halliburton's asbestos-liability problem, which ended up costing $5.1 billion and threatened to bring down the entire company. All these issues have contributed to a distinctly underwhelming bottom line: Since August 2000, when the current CEO took over, Halliburton has reported net losses of nearly $2 billion.

So Halliburton is awash in problems--they're just not what you think. The politician who ran the company from 1995 to 2000 will not be remembered as a great, or even good, CEO. But the real story is the businessman who replaced him. Halliburton isn't a company consumed by systemic fraud and corruption. It's simpler than that. The problem is just poor leadership.

In interviews for this story, a single question kept popping up: How does David J. Lesar, Dick Cheney's successor, survive as chairman and CEO of Halliburton?

"I don't know how the guy still has his job," says one former Halliburton executive. "Usually corporate America's not that forgiving." Considering all the company's problems, even his fans are amazed that he endures. Lawrence Eagleburger, a former board member (and onetime Secretary of State) who calls Lesar "stupendous," says, "I frankly am surprised that there weren't more calls for getting rid of him."

Lesar's saving grace has been Halliburton's stock, a subject he talks about a lot. With the asbestos issue now put to rest and energy prices soaring, shares have enjoyed a big run-up from the dark days of early 2002, when asbestos panic sent them crashing below $9. The stock has recently traded at about $44. The problem is that when Lesar took over as CEO, Halliburton traded at $54.

At 51, Lesar is tall and a bit jowly, with a resemblance to the actor Edward Herrmann. Dressed in shirtsleeves for our meeting, he is articulate and low-key, unfazed by any question. Still, it becomes clear why, though he is sometimes admired, Lesar is rarely loved; in a dirty-fingernails business, he retains a certain detachment, a bean counter's awkward feel for the art of human relations. Trained as a CPA, Lesar spent 16 years at Arthur Andersen, though he apparently doesn't view that as a PR plus. His corporate biography omits his time at the firm that did Enron's accounting. (Cheney's official bio on the White House website, in turn, never mentions the word "Halliburton.")

Lesar, who says he is "paid to solve problems and move on," agrees that he seems to have been buried in thorny issues lately, adding, "We jokingly refer to 2004 as the year of the perfect storm." But he blames much of the criticism he faces on disgruntled former employees. There is indeed much Lesar-bashing among former Halliburton executives who were fired or forced out during serial "restructurings" in recent years and have reason to harbor a grudge. But there is also scorn from other quarters about the company's leadership and direction, which has lurched from strategy to strategy.

In January, Lesar announced new steps to dress up Halliburton for Wall Street by shutting down its operation in Iran and casting off KBR altogether. He hopes that all this will allow the world to see the real Halliburton--and price his company as a "pure play" energy-services company, perhaps even awarding it the premium multiple enjoyed by longtime rival Schlumberger. Lesar revels in the progress he's already made by ending the asbestos crisis. "The market abhors uncertainty," he says. "From the day we were at the bottom to our market close yesterday, there's been a $17 billion increase in our market cap. Probably not a bad tradeoff."

Halliburton is actually a combination of two storied--and very proud--companies. One side is the oilfield-service business, one of two premier players in an industry that provides the technology and muscle needed to extract hydrocarbons from the ground. Halliburton, known as "Big Red," specialized in brawn. Its business dates back to 1919, when Erle Halliburton, a strong-willed Tennessean with little money but big ambitions, landed in the booming Oklahoma oilfields. He peddled the virtues of "cementing" wells: lining the shaft with cement, which seals it from water contamination and cave-ins. Today cementing is an essential step in drilling wells--and Halliburton dominates this piece of the oilfield business.

Even as it diversified, adding new technologies and services and going public in 1948, Halliburton never attained the prestige of Schlumberger, which specialized in "wireline logging"--the more sophisticated (and lucrative) art of sending sensing devices into a well to evaluate oil and gas formations. Erle hated Schlumberger, and its Paris origins only made it more loathsome. In 1938 a rare meeting between the two companies, convened over a patent dispute, ended abruptly when Erle jumped to his feet. "I'll tell you how to settle this lawsuit!" he announced. "You Frenchmen go back where you belong!" Schlumberger was always bigger, smarter, and more beloved on Wall Street; Erle's company has a chip on its shoulder to this day.

The second big piece of the company, the engineering and construction division now called KBR, grew up as Brown & Root. Brown & Root is best known as the business whose founders bankrolled Lyndon Johnson's rise. In return, L.B.J. funneled big public projects to the company, then a lowly Texas road builder. Halliburton bought Brown & Root in 1962, having met the Brown brothers' chief conditions: It wasn't in the construction business, and it was rabidly anti-union.

There was a certain synergy about the marriage, at least in theory. The oilfield business tied up lots of capital, but its jobs enjoyed juicy profit margins--at least during good times. Brown & Root's big projects produced skinny margins but generated lots of cash, which helped fund the energy side. There was even the thought that Brown & Root would cushion the brutal boom-and-bust oil-patch economic cycle: When drilling was down, construction and engineering might be up.

Brown & Root built government megaprojects: the Johnson Manned Spacecraft Center outside Houston; airbases in Vietnam; a 24-mile causeway across Louisiana's Lake Pontchartrain. But more than 80% of its business was with corporate customers--including a booming trade in offshore drilling platforms, an industry it helped invent. The company's engineers prided themselves on being able to build anything, anywhere--"Brownbuilders," they called themselves.

For two decades the combined company grew like crazy. By 1981 revenues had soared to $8.5 billion, profits were $674 million, and Halliburton employed more than 110,000 workers. This was Halliburton's Golden Age, and the company became a Wall Street darling, receiving praise not heard today. One analyst called it "a superb, well-managed, strongly financed growth company."

But when the oil bust hit, both sides of the business dried up. In 1986 the company lost $515 million; the payroll fell to 47,000. The tough times continued into the early 1990s under CEO Tom Cruikshank, who consolidated the oilfield side, merging the ten service companies Halliburton had collected into a single business called Halliburton Energy Services. Almost 3,000 executives lost their jobs. "It was awful," says Cruikshank.

This wrenching reorganization was completed with the help of a new vice president hired from Arthur Andersen: 40-year-old Dave Lesar. Lesar had no experience operating a business. He'd spent his entire career at Andersen, where he'd done work on the Halliburton account. But "he was impressive from day one," Cruikshank says. "He dug in and learned a lot in a hurry. He was a performer. And he's tough." In August 1995, Lesar was elevated to CFO of Halliburton. Three months later he had a new boss: Dick Cheney.

The theory of hiring a career politician to run a FORTUNE 500 company went like this: Halliburton desperately needed more work overseas (the hot area in the energy business), and no one had better contacts than Cheney--with heads of state, no less! Cheney would serve as Halliburton's global salesman-in-chief. The messy details of actually running the company? He could delegate those to someone else.

That person, of course, would be Lesar--who had only slightly more business experience than Cheney. Within a year of his arrival, Cheney had fired Tommy Knight--a respected 32-year Brown & Root veteran--and named Lesar as CEO of Brown & Root, in addition to his duties as CFO of Halliburton. In May 1997, Cheney elevated Lesar to president and chief operating officer. Cheney was "hands off, very much a delegator," Lesar later told the New York Times. "On major types of things, I would tell him what the decisions were."

The central thrust of Cheney's five years as CEO was to make Halliburton much bigger, into a sort of energy-services superstore. It would have the heft to provide what he called "integrated energy solutions," handling everything from drilling to offshore-platform construction, and thus could tackle giant projects that few rivals could handle, especially for national oil companies overseas. It would also require Energy Services and Brown & Root--which had never had much to do with each other--to operate as one.

Cheney began by moving Brown & Root's offshore business into the energy-services side. To force-feed his consolidation, he established a powerful "shared services" division, run by Lesar, to control administrative functions companywide, from purchasing to finance to hiring. Project managers (especially at Brown & Root) despised this new creation, saying it gave so much power to support staff that it kept them from doing their jobs. "It was like the Soviet navy," says one former executive.

Then, in February 1998, Cheney made his big move: the $7.7 billion purchase of Dresser Industries. Dresser, based in Dallas, was nearly as big as Halliburton, with separate oilfield and engineering divisions of its own. (The engineering business, M.W. Kellogg, would be merged with Brown & Root to form Kellogg Brown & Root, or KBR.) But the combination seemed complementary; only a few of their businesses overlapped. It also made Halliburton the biggest player in the industry--bigger even than Schlumberger! Cheney declared the deal "a win-win combination for both companies' shareholders, customers, and employees." He would later boast on the campaign trail that during his tenure, "we went from being a second-tier, second-rank energy-services company to being the biggest in the world."

It didn't take long for this colossus to start generating giant headaches. It turned out that Halliburton had bought Dresser near the top of the market, at a 16% premium. By late September, when the purchase closed, oil prices had plummeted to $10 a barrel. "From a timing standpoint," acknowledges Lesar, "it couldn't have been a worse time to complete a merger." One of Cheney's first moves after the deal closed was to cut 10,000 jobs.

The integration of the two companies was also ugly. Cheney had pronounced them "an outstanding business and cultural fit." But Halliburton's top-down culture couldn't have been more different from Dresser's decentralized approach. And there would be no question who would prevail in this "merger of equals": Dresser's executive talent fled in droves. "Most of them left because they felt they had been shoved aside," says Lawrence Eagleburger, who was a Dresser director before joining the Halliburton board. "There was certainly a feeling that they had been badly used."

But an even bigger problem was that due diligence--in which Lesar, as COO, had played a key role--had been carried out too quickly. Former Dresser president Donald Vaughn, who left Halliburton in 2001, later said the two sides felt they could complete their investigation of each other's operations "in very short order" because they knew each other so well.

The prospectus sent to both companies' shareholders for approval contained a laundry list of business risks posed by the merger--everything from changes in the price of chemicals to political conflict in Nigeria. Unmentioned was the biggest risk of all: asbestos liability.

By the time Cheney's deal with Dresser went down, asbestos was already one of the biggest legal onslaughts in history. Most of the people filing suit had yet to show any symptoms of asbestos-related disease and had experienced only fleeting exposure to the substance. In addition, many of the companies being sued had only a distant relationship to the exposure. No matter: By 1998, asbestos litigation had bankrupted more than two dozen companies.

Dresserfaced 66,000 claims alleging its responsibility for asbestos-related health problems, most dating back to a former Dresser subsidiary in Pittsburgh, Harbison-Walker. Until the 1970s, Harbison-Walker had used asbestos in industrial products it sold, such as insulating bricks and coatings. Dresser had spun off the division in 1992 but retained partial liability.

Halliburton officials concluded that its problem could be "managed." For one thing, they had experience with a small number of claims filed against Brown & Root, which had used asbestos in construction projects decades earlier. For another, the inflow of new claims seemed to be holding steady, and most were being settled cheaply. Both companies also had insurance, and Dresser had an agreement that Harbison's new owner would pick up much of the asbestos tab.

The situation rapidly deteriorated. It turned out that the new owner of Harbison-Walker, which had promised to cover claims filed after 1992, had demanded in mid-1998 that Dresser foot more of the bill. (Halliburton, which hadn't known about the request before the merger closed, dismissed it as "without merit.") Next, a court ruling that kept a lid on new lawsuits was lifted, and the number of claims soared. (Halliburton insisted they would all be resolved "without material effect.") Then, an insurer for Brown & Root's claims--itself a former Halliburton subsidiary--sued to get off the hook, arguing it hadn't been properly informed about the asbestos problem. (Halliburton called the suit "without merit.") When it lost, Halliburton appealed, calling the court ruling "wrong" and a reversal "very likely." When it lost again, Lesar expressed "surprise." The defeat would cost Halliburton $80 million. Still, Lesar insisted the asbestos problem would have no material effect.

By 2001, Wall Street had begun to doubt Lesar's prognosis, and Halliburton shares started sinking. In September, Dresser was one of the losers in a $130 million Texas jury award. Yet five weeks later Lesar told analysts, "There have been no adverse developments at all with respect to the Harbison-Walker situation." He added that the asbestos "discount" on Halliburton's stock was "way overdone." (A Halliburton spokeswoman later explained why the company didn't disclose the award: It wasn't final, the company expected it to be reversed on appeal, and the claims were insured.)

On Dec. 7, Halliburton issued a press release disclosing three big asbestos awards, and Halliburton shares fell 42.5% in a day, to $12. By year-end, Halliburton faced 274,000 claims. In January 2002, Moody's cut its debt rating. A month later, Harbison-Walker filed for bankruptcy, dumping all its liability in Halliburton's lap. The stock fell below $9. Wall Street worried about Halliburton's survival.

Bert Cornelison, Halliburton's general counsel, says he believed the company would overturn the big awards on appeal or settle them for far smaller amounts. "None of this really troubled me," he says. "But it certainly troubled the stock market. When the stock traded at $8.50, I realized I was going to be asked for other alternatives."

Later that year, Halliburton found one: a "prepackaged bankruptcy," which allowed it to place just pieces of the company in Chapter 11, retain control of the business, and avoid wiping out shareholders. In the end, the pricetag soared far beyond company projections: to $5.1 billion--$2.8 billion in cash and 59.5 million shares of Halliburton stock. (Insurance will reimburse about $1.4 billion.) With the needed court approvals in hand by the end of 2004, the money and shares went into a trust to settle present and future claims, resolving the matter for good. And with each step toward resolution, Halliburton's shares kept moving back up.

Today Lesar--who was awarded a half-million-dollar bonus by the Halliburton board in December 1998 for his part in "bringing the Dresser merger to its successful conclusion" (Cheney got $1.15 million)--views solving the asbestos problem as the foremost achievement of his CEO career. "Was the price we paid worse than we thought?" he asks, sounding like Donald Rumsfeld. "Given what's happened with asbestos, certainly. People will quibble with the price. The reality is, we got through it." Lesar insists that his company's due diligence in the Dresser deal was entirely "appropriate." As for criticism of the move? "I think that's your classic business hindsight mentality going on."

David Austern disagrees. Austern is general counsel of the Manville Personal Injury Settlement Trust and is one of the nation's top experts on asbestos litigation. As Austern explains it, the issue was never what asbestos had cost Dresser or the rate of new claims. It was the certainty that asbestos would cost more in the future, as plaintiffs lawyers recruited more clients and targeted surviving companies with ever more remote connections to the problem. "Unless you were deaf, dumb, and blind, by early 1998, if not sooner, you had to know about the dangers of asbestos. No one's asbestos issue is 'under control.' People have done stupider things, but it was a known problem."

Lester Brickman, a law professor at Yeshiva University and a frequent consultant to corporate defendants on asbestos, predicted in the mid-1990s that the only limit on companies' asbestos liability would be the value of the companies themselves. "The formula that I'd developed was n+1--where n stood for the last dollar available from the last defendant. Halliburton had the same attitude that every other major corporation had in the middle to late 1990s--that asbestos was a very expensive but confinable liability. They were wrong." Brickman says the leveling off of claims was only a calm in the storm while court decisions were under review. "It was clear the stability was not going to last," he says. "Had Halliburton dug into the underworld of asbestos litigation, due diligence would have shown it was impossible to quantify the liability of Dresser. And this inability would have been at least a red flag--if not a stop sign--with regard to the acquisition." Thus Halliburton purchased one of the biggest asbestos problems in corporate America.

Among Halliburton's critics on the issue is John Harbin--like Lesar, a onetime Arthur Andersen accountant who went on to become CEO of Halliburton. Harbin ran the company from 1972 to 1983, during Halliburton's Golden Age. Now 88, he keeps a sheet of paper in the top drawer of his desk in his Dallas office. On it, he has jotted the annual profits of the company during each year of his tenure--and those of the three men he gently labels "my successors." Harbin shakes his head at the impact of the Dresser deal. He believes Lesar deserves credit for solving the asbestos problem, but that Halliburton never should have faced the mess in the first place. "Cheney bought Dresser in 1998 and paid a 16% premium," says Harbin. "With that acquisition he bought $4 billion of asbestos liability. Would you pay a 16% premium to buy a $4 billion asbestos liability? That doesn't appeal to me."

Norman Chambers, who spent 20 years inside Halliburton, remembers the brutal scrutiny his construction projects faced from Tommy Knight, the veteran Brown & Root CEO who was fired in 1996. Skeptical teams of top executives would challenge every aspect of a job--from cost estimates to staffing to materials. "Norman," Knight would tell him, "we're trying to keep from losing our ass."

In Halliburton's 2000 annual report, new CEO Dave Lesar wrote proudly of winning the biggest fixed-price offshore contract ever--a $2.5 billion job in Brazil's Barracuda and Caratinga oilfields, 100 miles out in the Atlantic. Lesar viewed the deal as proof of the new Halliburton's ability to combine oilfield work with construction--and a choice opportunity to beef up the skinny 4% profit margins typical at KBR.

Instead, Halliburton would "lose its ass."

Lesar had championed fixed-price projects even before becoming CEO. In 1996, after taking over Brown & Root, he talked about how such deals could boost profits: "Lesar's prescription for Brown & Root," a story in Engineering News-Record noted, "is to take on more risk on turnkey, lump-sum engineer-procure-construction contracts ...." In a July 2000 interview, when asked what project best defined "the Halliburton of the future," Lesar cited Barracuda as "a potential model demonstrating the capabilities of the entire Halliburton Group."

Brown & Root had done fixed-price deals over the years, of course, but it did so with caution, choosing projects with familiar designs and customers. Fixed-price work can be much more profitable for the contractor than the usual "cost reimbursable" approach, because the contractor assumes the risk and reaps the upside if he manages the project efficiently. But such deals are fraught with peril. If the project were to go over budget, Halliburton would have to eat the cost unless the customer agreed to pay more.

And there was no riskier deal than Barracuda-Caratinga. For one thing, it was huge: It involved transforming a pair of 30-year-old supertankers into floating production, storage, and offloading platforms, known as FPSOs. Each of the supertankers would be massively refitted to process 150,000 barrels of oil a day and would hold two million barrels for offloading onto tankers. The design would involve years of shipyard work, guided by 100,000 engineering documents.

And that wasn't the half of it. Halliburton would be doing all this for a tough-as-nails customer: Petrobras. The Brazilian national oil company was known for forcing contractors to absorb cost overruns on their projects--no matter who was at fault. To make matters worse, Petrobras insisted that 40% of the work be done in Brazil. This meant using a shipyard that had been mothballed for years and training thousands of workers. One former KBR executive, who spent decades working in the offshore business, drolly sums up the venture this way: "You wouldn't really want to go into a country where you'd never worked, on the biggest contract ever, using a shipyard and workers that had never done this before. In hindsight, it's not something a wise person would want to do." But Dave Lesar very much did. Four former Halliburton offshore executives say he was deeply involved in the Brazil project from early on--something the company now denies.

In October 1999, Halliburton was named as "preferred bidder." In July 2000 the contract was signed. Work commenced almost immediately--and so did the problems. In negotiations with Petrobras, Halliburton had reduced its bid in the belief that it could cut costs by building two identical FPSOs. But Petrobras insisted on a different design for each of the oilfields. Its specifications for the project also required thousands of oversized valves, each weighing about 20 tons, far larger than Halliburton thought were needed (or had priced) for the FPSOs' production capacity. Then the hulls needed unexpected repairs. Some of the shipyard work had to be redone. And on it went.

More than a year into the work, Halliburton dispatched a new team of project managers to Brazil. But the situation only kept getting worse. Barracuda recorded a $117 million loss in 2002 and a $238 million loss in 2003. For a while Lesar kept insisting that Halliburton would in the end make money on the project. But by last year, when a final settlement with Petrobras produced another $407 million loss, running the grand total up to $762 million, it became clear that Brazil was Halliburton's Waterloo.

The two platforms are now onsite in the Atlantic, more than a year late, producing oil. Lesar projects that they will incur no further losses.

Cornelison, the general counsel, believes that Barracuda-Caratinga was doomed financially from the start. "It wasn't bid to where it should have been bid," he says. Andy Lane, a Halliburton executive sent into KBR to deal with problems in mid-2004 (he was named Halliburton COO four months later), says, "The risks associated with it were underestimated," and Halliburton's margin was "negotiated away." He adds, "It should have been priced much higher."

And who was responsible for this disaster? Lesar doesn't exactly raise his hand. He notes that the deal was signed before he became CEO. "That was part of the strategy that was espoused around the merger of Dresser and Halliburton," he says, describing Barracuda-Caratinga as "a strategy error with respect to what the merger gave us." He notes that he has now barred Halliburton from bidding on such fixed-price projects, several of which have lost money. Says Lesar: "The decision I could make was never to pursue jobs like that again."

And then there's Iraq. As Dave Lesar sees it, America should be praising, not burying, Halliburton for its work there. His company was handed a far larger task than it ever imagined, he says, and it rapidly assembled a logistical juggernaut involving billions of dollars and a workforce of 46,000. What Halliburton did is tantamount to "creating a FORTUNE 270 company in 18 months," he says. "In any other context, it would be, 'Zero to 46,000!'--this wonderful entrepreneurial success story!"

"Of course, a company that grew that fast is going to have growing pains," Lesar quickly adds. But "every little stumble is held up and magnified in the political process. If you look at what we've done on the ground, it's a pure miracle." In the Balkans, where Halliburton provided similar military support, "you didn't hear any of this stuff. What we did there was good. What we've done in Iraq is good --to the third power!"

Halliburton's task in Iraq truly is monumental. KBR provides all manner of services--food, water, shelter, mail delivery, laundry--for more than 150,000 soldiers. Much of that work is carried out in desert conditions and at considerable risk--62 Halliburton employees and subcontractors have been killed, and several times that number have been wounded. But then, no one really questions Halliburton's skill at tending to the troops. The real issue is the company's ability to manage and account for what it is spending. And while it's certainly true that many of the attacks on the company have been politically motivated, not all of them are. In fact, what's far more damning than the partisan attacks has been the scrutiny of Pentagon auditors, the General Accounting Office, the Inspector General of the Coalition Provisional Authority, and the Justice Department.

Of course, it's hard to worry about receipts when mortar shells are dropping around you. But the disarray and poor management depicted in the government reports--and vividly described to FORTUNE by former KBR project managers in Iraq--made a chaotic situation immeasurably worse.

Virtually all of Halliburton's $11 billion in government work in Iraq has been performed under two contracts. It is the smaller of the two, the $2.5 billion Restore Iraqi Oil (RIO) agreement, that has generated the most suspicion about Cheney's hidden hand, because it was awarded secretly, on a no-bid basis, in March 2003, on the eve of war. Under this cost-plus contract, Halliburton was hired to put out oilfield fires and rebuild Iraq's oil infrastructure. It is under this contract that KBR charged infamously high prices to ship gasoline into Iraq. The premise for the no-bid award was that Halliburton was already briefed on classified military plans for the war and would be best able to move equipment and staff into the country quickly. Halliburton receives a fee of 2% of its costs, plus a performance award of up to 5%.

Cheney and others in the administration vehemently denied that he had anything to do with RIO. But last June Time revealed an e-mail from an Army Corps of Engineers official noting that "action" on the Halliburton contract had been "coordinated" with the Vice President's office. While this was certainly tantalizing--and was accompanied by other evidence suggesting political appointees played a role in Halliburton's selection--the nonpartisan GAO concluded that the no-bid award followed proper procedures. After ten months the job was split in two and competitively bid. Halliburton was awarded the oil work for southern Iraq, while the north went to another contractor.

The biggest piece of Halliburton's Iraq work--an estimated $8.5 billion in billings so far--comes under an Army-support contract called LOGCAP, for Logistics Civil Augmentation Program. Its origins predate Cheney's time at Halliburton. He did play a role in creating the LOGCAP business during his years as Secretary of Defense, but it was long before U.S. soldiers marched into Baghdad.

Historically, Halliburton had always worked for the government on a project-by-project basis. (Management was never keen on working for Uncle Sam. Erle Halliburton was rabidly antigovernment, ranted about excessive taxation, and at the height of the Depression, even banned the company from hiring anyone who had been on "the dole.") But during its tough times in the late 1980s, Brown & Root, on the advice of McKinsey consultants, had established an ongoing government operation. Much of the appeal came from a Pentagon initiative to shrink the standing Army and outsource support work.

Halliburton set up a new subsidiary, Brown & Root Services, and hired an executive from the outside, Arthur Stephens, to run it. Stephens says he quickly learned rule one of government contracting: Know what your costs are--and document them. This, he says, is almost as important as doing the actual work; government contracting requires detailed documentation of everything, and maintaining control of the paperwork is a critical part of managing the business. The new Halliburton division's first job was providing vehicle-fleet maintenance for the city of Houston. Soon it was winning contracts to run and maintain military bases, including the U.S. Air Force's operations in Turkey and a big shipyard for the British navy.

Halliburton began supporting the Army's deployments in 1992, when it beat out 36 other bidders to win the five-year contract now known as LOGCAP I. LOGCAP started out small, as a $3.9 million contract whose first task was to plan how a private company would feed and house up to 20,000 troops in various military hot spots for 180 days. Brown & Root would be reimbursed for its costs and receive 1% profit as well as a performance fee, set by a Pentagon review board, of as much as 8%.

To Stephens, that kind of profit margin was critical. The company was agreeing, on a moment's notice, to deploy staff, equipment, and supplies anywhere in the world. Halliburton's attitude, says Stephens, was "I'm willing to rip my company apart, but you've got to pay me to do it." Deployments quickly followed: Somalia in 1992; Haiti, Rwanda, and Kuwait in 1994; the Balkans in 1995.

When Dick Cheney arrived as CEO that year, the government group celebrated. Who could do more to build their Pentagon business than the former Secretary of Defense? But Cheney, who traveled widely to drum up oil-services work, wouldn't make any sales calls for the government business. It is unclear whether this was a matter of principle or political caution. (He told one executive, "I don't want to generate any headlines.") In fact, Cheney was skeptical about the entire line of business, according to those who worked for him. Lesar says, "I don't think he viewed the U.S. government as a particularly good customer."

In 1997, LOGCAP was rebid--and Brown & Root lost the work to a company called DynCorp. But the Clinton-era Pentagon allowed the Halliburton subsidiary to hang on to the biggest piece of LOGCAP work, in the Balkans, reasoning that a transition there would be disruptive.

As it turned out, Halliburton made decent money on government work during the Cheney years. The Balkans deployment alone generated $2.2 billion in revenues through 2000, and Halliburton always received at least 98% of the maximum award fee. The military was clearly delighted with Halliburton. As described by a GAO report, one Balkans project--the construction of a 5,000-man base camp--"required the Army and [KBR] to build the equivalent of a small town in a wheat field in a few months." Gone were the days of sleeping in foxholes and eating out of tin cans; the KBR-backed Army slept on cots and ate three hot squares in mess halls.

Even then, the issue wasn't whether KBR did enough for the military; it was whether it did--and spent--too much. The GAO said some military brass wondered whether the level of services "may be above and beyond what is really needed." There were reports that the contractor was so overstaffed in the Balkans that offices were cleaned four times a day. Projects had a way of escalating far beyond what was projected. The GAO called Pentagon outsourcing contracts "a high-risk area of government spending."

In 2001, the LOGCAP contract came up for bid again, this time for a ten-year term. Randy Harl, a company veteran then in charge of the restructured KBR division that included government work, was eager to reclaim the business. So were others at the company: LOGCAP was seen as a magnet for other, higher-margin contracts. So KBR bid a price that was shockingly low. In addition to being reimbursed for what it spent, Halliburton would get a base fee of 1% and a maximum performance award of just 2%. A former Halliburton executive involved in the bidding still winces at the deal. Between litigation expense and the amounts that the government might disallow in Iraq, he says, "LOGCAP could be the first cost-plus contract in history that's lost money."

The Iraq deployment was Halliburton's toughest LOGCAP job yet, involving seven times as many troops as in the Balkans, far closer to active combat. And unlike in Bosnia, where it did virtually all the work itself, KBR handed off most of its business in Iraq to subcontractors--or "subs," as they're called.

But it was utterly unprepared to manage them. According to key former KBR executives who worked in Iraq, the company never assembled the teams needed to negotiate and supervise subcontracts, purchase supplies and equipment, and document what it was doing. "The first people I needed were subcontract administrators, and what I got were carpenters and plumbers," says one former KBR project manager. "The system to execute the work was woefully undermanned."

"The top LOGCAP managers were crying for people," says another former KBR executive in Iraq. "Two or three times a day we would call, asking for procurement people, IT help, finance people to keep the books. Houston couldn't get them to us. The company did not throw enough resources at the problem soon enough. There comes a point where you lose control. People started talking shortcuts--'We'll do it verbally, and we'll document tomorrow.' Well, tomorrow you have more work. Eventually it just collapses of its own weight." Dozens of KBR subcontractors have gone unpaid for months; at least two have filed suit.

Because of the staffing shortages, sound business procedures simply weren't followed. For example, according to a company SEC filing, the Pentagon is withholding payment on $224 million in dining-hall charges. Auditors found that, among other problems, Halliburton was charging for meals that were never served to troops. A former KBR executive told FORTUNE of a case in which a sub billed for feeding 4,700 soldiers every day for months, when no more than 2,500 ever showed up to eat. In fact, the sub had been hired to provide for 4,700 soldiers, but no one at KBR had told the sub to cut back.

So far, the reports issued by Pentagon auditors, the GAO, and other agencies have found more than $1.8 billion in "unjustified" or "undocumented" charges--as well as sweeping systemic problems in Halliburton's record keeping, systems, supervision, and staffing. The reports complain that the company has refused to provide required information--or has misled auditors about its efforts to seek competitive prices. Pentagon auditors have recommended that the federal government withhold payment on 15% of Halliburton's LOGCAP billings in Iraq.

Several problems that have surfaced are of the jaw-dropping variety--subs charging $100 to wash a 15-pound bag of laundry, and so forth. Especially telling was an October 2004 Pentagon audit of the RIO contract. Out of $875 million in charges it examined, $108 million was deemed "questionable" or "unreasonable." This included Halliburton's claim to have spent $27.5 million to ship to Iraq liquefied gas it had purchased in Kuwait for just $82,100--a fee the audit calls "illogical." (A Halliburton spokeswoman responded that the company delivered "vital services for the Iraqi people at a fair and reasonable cost, given the circumstances.")

In March, a federal grand jury in Illinois filed the first criminal charges involving Halliburton's work in Iraq. Jeff Alex Mazon, a 36-year-old former Halliburton procurement manager who had worked for the company for seven years, was charged with fraud, accused of taking a $1 million kickback for awarding an inflated government subcontract to a Kuwaiti firm. The managing partner of the Kuwaiti firm, a significant KBR sub, was also charged.

Halliburton executives correctly note that their own audit uncovered the problem, which prompted the dismissal of two employees and a $6 million repayment to the government. They say that after some initial problems in Iraq, they have moved aggressively to address the challenging nature of doing business in a war zone--and that Pentagon audits are merely part of the normal give-and-take with the government, during which Halliburton will have a chance to correct problems and justify its charges. "People need to wait until that process is completed before they make a judgment as to our performance in Iraq," Lesar says. "Investigations and audits and questions from regulators and customers are a routine part of being a government customer."

Despite everything that's gone wrong in Iraq, in Brazil, and with the asbestos litigation--not to mention the Iran situation, the bribery investigation in Nigeria, the SEC issue, and all the other problems--Lesar seems more firmly entrenched than ever. During 2004, the top executives at both of the company's major operating units departed. Randy Harl, the 30-year Halliburton veteran who ran KBR, took "early retirement" at the age of 54. John Gibson, the admired and ambitious boss of the oilfield business, which generates most of the company's profits, quit after Lesar made it clear that he didn't plan on leaving anytime soon. Neither was replaced at the operating units. Instead Lesar named a 45-year-old protégé, Andy Lane, as Halliburton's chief operating officer.

The latest changes continue an almost unending run of management shuffling. In five years as CEO, Lesar has had three CFOs and two chief operating officers. Many key operations executives in Iraq have been replaced; a newly hired COO for U.S. government contracting remained at Halliburton less than a year. Energy-services managers have been leaving too. "There has been just unbelievable turnover of division presidents and senior management," says a Wall Street analyst who has followed Halliburton for more than a decade. Company spokeswoman Wendy Hall responds, "Perhaps this analyst doesn't understand the nature of our business. Change is a constant in our businesses."

Lesar has also presided over a string of restructurings. Not long after becoming CEO, he reversed the decision to move the offshore business into energy services, placing it back inside of KBR. In 2001, he moved to impose the Halliburton name across the entire company. In what Lesar billed as "an important evolution for the company," KBR became Halliburton KBR. The program was dropped after a year. There have been multiple rounds of dismissals and cost-cutting in the name of producing a "leaner, flatter organization."A new effort to cut another $100 million in costs from KBR is now underway.

The widespread view is that much of the surgery is intended to dress up KBR for spinoff or sale, a process Lesar says may take several quarters, to allow the division time to produce a track record of decent profits. It certainly hasn't done that lately. In the fourth quarter of 2004, KBR booked revenues of $3 billion--but didn't make a penny. (Over the same period KBR's Iraqi operations earned $13 million on revenues of $1.7 billion--a margin of 0.8%.) The oilfield business, by contrast, generated an operating margin of 17.1%.

Lesar says he has decided to part with KBR because "it overcomplicates having to tell our story in the marketplace. We have a very good energy-services business that has been overshadowed by some of the issues we've had at KBR and some of the political dynamic .... [Investors] want to see those two businesses separated."

And what of the Halliburton board? Current directors--including such tough-minded figures as former American Airlines chief Bob Crandall and Texas oilman Ray Hunt--didn't return FORTUNE's phone calls. If compensation is any indication, the directors don't blame Lesar for much of anything: His total compensation package in 2004 added up to $11.4 million. His bonus for the year included a "discretionary cash payment" for his "ongoing efforts" to clean up the asbestos mess. (Asked about the $2 billion in total losses on Lesar's watch, the company responded, "The stock price improvement over the past three years speaks for itself; it has quadrupled. We are the only company to accomplish a non-recourse asbestos settlement without bankrupting the whole company, and the financial performance, excluding the $5 billion charge for the asbestos settlement, has been good and continues to improve.")

For his part, Lesar acknowledges that some of his critics expected to see him gone by now. "There were those that thought asbestos would burn me out," he notes, with an edge of defiance in his voice. "Were 2002 and 2003 and 2004 tough years?" he asks, surveying the majority of his tenure. "Sure. Yeah. But I'm energized. I'm looking forward to the future. I want to lead Halliburton for as long as the board feels I'm the right person to do that." ■

FEEDBACK pelkind@fotunemail.com