(FORTUNE Magazine) – In the world of retailing, Wal-Mart is the unstoppable, insatiable force. With $247 billion in revenues--and growing 15% a year--it reduces downtown shop owners to quivering jelly and once-formidable competitors, like Kmart, to bankruptcy. Wal-Mart CEO Lee Scott rules the commercial strip the way Julius Caesar once ruled the Roman republic.

Except, that is, for a solitary rebel-held province where a company 20% the size of Wal-Mart has made a monkey of the 800-pound gorilla. In the retail niche of warehouse clubs, the irresistible force is an irresolute flailer. During the past ten years Wal-Mart has gone through five CEOs and countless stratagems at Sam's Club trying to assume its customary command. All have been thwarted by Costco Wholesale, the master of the cavernous space.

Consider some figures. Sam's Club has 71% more U.S. stores than Costco (532 to 312), yet for the year ended Aug. 31, Costco had 5% more sales ($34.4 billion vs. an estimated $32.9 billion). The average Costco store generates nearly double the revenue of a Sam's Club ($112 million vs. $63 million). Costco is the U.S.'s biggest seller of fine wines ($600 million a year) and baster of poultry (55,000 rotisserie chickens a day). Last year it sold 45 million hot dogs at $1.50 each and 60,000 carats of diamonds at up to $100,000. Chef Julia Child buys meat at Costco. Yuppies seek the latest gadgets there. Even people who don't have to pinch pennies shop at Costco. "I like bargain securities," says Berkshire Hathaway vice chairman Charlie Munger, a Costco shopper, investor, and director. "Why shouldn't I like bargain golf balls?"

The one man Wal-Mart fears doesn't seem fearsome in person. At 66, he has hair as thin as his company's margins, and he seems more like a twinkle-eyed grandfather (which he is, eight times over) than a killer retailer. His office in suburban Seattle overlooks the parking lot of the Costco next door. The folding chairs for visitors bear Los Angeles Lakers logos. The lamp on his desk is festooned with old nametags. One wall has two Swiffer mops leaning against it; another, along the hallway, was knocked down to make the boss viewable and available to passing colleagues. Or they can pick up the phone and call, since he answers himself, with a brusque "Sinegal."

James D. Sinegal, the president and CEO of Costco, has no palace guard and no profile to speak of, particularly compared to a retail legend like Sam Walton. Yet he's the guy who in 20 years has taken Costco from a startup to the FORTUNE 50 using, as surely as Mr. Sam, highly distinctive practices. He caps Costco's markups at 14% (department store markups can reach 40%). He offers the best wages and benefits in retail (full-time hourly workers make $40,000 after four years). He gives customers blanket permission for returns: no receipts; no questions; no time limits, except for computers--and even then the grace period is six months.

But some of the practices that made Costco great have lately come under attack by Wall Street. The company's margins have been squeezed by rising labor costs and by Sam's latest run at its nemesis. Costco has twice reduced its earnings outlook this year; after the second warning, in August, its stock dropped 21%, to $29. For the fiscal year ended Aug. 31, Costco's earnings rose 3%, to $721 million, on a 10% rise in revenues. The stock has climbed into the mid-30s, though it's well below its all-time high of $58 in May 2000. Analysts have pounded on Sinegal to trim the company's generous health benefits and to otherwise reduce labor costs. But he's taken only limited steps in that direction, like modestly increasing employees' share of health-insurance premiums. That doesn't satisfy critics like Deutsche Bank analyst Bill Dreher, who recently wrote, "Costco continues to be a company that is better at serving the club member and employee than the shareholder."

Sinegal just shrugs. "You have to take the shit with the sugar, I guess. We think when you take care of your customer and your employees, your shareholders are going to be rewarded in the long run. And I'm one of them [the shareholders]; I care about the stock price. But we're not going to do something for the sake of one quarter that's going to destroy the fabric of our company and what we stand for."

What Costco has come to stand for is a retail segment where high-end products meet deep-discount prices. Warehouse stores are only a small slice of the U.S. retail universe--4% or so--but they matter. They've been a growth category in a tepid period for retailing, and they've redefined discounting. Time was when only the great unwashed shopped at off-price stores. But warehouse clubs attracted a breed of urban sophisticates--detractors would call them yuppie scum--attuned to what retail consultant Michael Silverstein calls the "new luxury."

These shoppers eschew Seiko watches for TAG Heuer; Jack Nicklaus golf clubs for Callaway; Maxwell House coffee (it goes without saying) for Starbucks. As Silverstein explains in Trading Up, a recent book he co-wrote, they eagerly spend more for items that make their hearts pound and for which they don't have to pay full price. Then they "trade down" to private labels for things like paper towels, detergent, and vitamins. Over the past two decades, this population has exploded as dual incomes have created more affluent households and widespread travel has refined tastes. Catering to that populace, Costco has exploded too. "It's the ultimate concept in trading up and trading down," says Silverstein. "It's a brilliant innovation for the new luxury."

So why didn't Sam's Club ride that wave? It had the resources of Wal-Mart at its inception, while Costco was started from scratch by Sinegal and Jeff Brotman, a Seattle entrepreneur who is still the company's chairman. At first glance the companies' business models appear much the same. They sell pallets full of goods out of no-frills boxes. They target small-business people and charge modest annual membership fees: $45 at Costco, $30 at Sam's. But while Sam's Club had a singular identity and sold distinctive goods in its early years, according to its first chief merchandiser, Rob Voss, its Wal-Mart-trained leaders eventually defaulted to their comfort zone: merchandising to the mass middle market and locating Sam's in small cities of 100,000 to 200,000. (Sam's Club executives declined interview requests for this story.)

Costco knew that its customer was a more sophisticated, urban creature. The company opened its first store in a gritty Seattle warehouse, then expanded to empty spaces in cities like Portland, Ore., and Tampa. "We understood that small-business owners, as a rule, are the wealthiest people in a community," says Brotman. "So they would not only spend significant money on their businesses, they'd spend a lot on themselves if you gave them quality and value. Jim [Sinegal] saw that you had to be just as much a merchant as Saks Fifth Avenue. You couldn't entice a wholesale customer with 20-pound tins of mayonnaise; you had to romance him with consumer goods."

After 20 years of strategic fits and starts, Sam's has begun to stock more high-end merchandise. But it's not clear that its core customers have a taste for luxury. On a recent reconnaissance mission to Sam's, Brotman was near a stack of Ralph Lauren Polo shirts when he overheard a customer say, "Can you imagine? Who in their right mind would buy a T-shirt for $39?" Says Brotman: "It was actually a very good deal; it would have cost $59 in a department store. But she didn't see the value, and Sam's built its customer base on people like that. It's very difficult to shift gears."

Jim Sinegal "got it" from the start because he was there at the start. He learned discount retailing from one of its pioneers, Sol Price, now a white-haired octogenarian. As a student at San Diego State in the 1950s, Sinegal worked part-time for a low-overhead, low-markup, low-price store called Fed-Mart. It was Price's first brainchild and, as Sam Walton freely admitted in his autobiography, the inspiration for Wal-Mart: "I guess I've stolen--I actually prefer the word 'borrowed'--as many ideas from Sol Price as from anybody else in the business."

Price sold Fed-Mart to a German company in 1975, was ousted, and soon dreamed up his next concept. He knew that small-business people were frustrated at the high cost of their supplies; they had little clout with vendors and paid big markups to middlemen. Price and his son Robert decided to open a store where, for an annual $25 fee, entrepreneurs could buy goods themselves at lower prices. Their Price Club almost died aborning after its 1976 opening because its customer base was too small. So the Prices added new categories of eligible members--and new products--until finally anyone could come in and shop as long as they paid the annual fee. The company grew from sales of $13 million at one warehouse in 1977 to $366 million at ten locations by 1982.

Other retailers began to investigate and imitate. One was Brotman, who wanted to start warehouse clubs in Seattle and in 1981 recruited Sinegal from Price Club to run Costco. Another was Sam Walton, who visited a Price Club in 1982 and opened his knockoff, Sam's Club, a year later. Sam's Club and Costco are two of only three surviving major players in the field today; the other is BJ's Wholesale Club, a smaller, East Coast chain.

From those common roots, Costco and Sam's developed very differently. "The biggest thing with Sam's," says Sol Price, "was that it didn't have a free hand to compete with Wal-Mart. There was this fundamental thing where they didn't want to kill Wal-Mart. The other problem was that Sam's didn't cater to the higher class of people that Costco did. Now, Jim has done a pretty damned remarkable job. He puts a great emphasis on quality and has moved into the food business and other new lines. We [the Prices] were very good at creating, but Jim was very good at developing."

In 1993 Costco bought Price Club. But what appeared to be a harmonic convergence of protege and mentor instead became a troubled marriage. Meshing the two at the top was uneasy and ultimately unhappy--a failed experiment in sharing leadership between Sol Price's biological son, Robert, and his surrogate son, Sinegal. After just eight months Costco spun off a separate company called Price Enterprises, led by Robert Price. The company evolved into PriceSmart, which operates warehouse clubs overseas.

Many of the Price Club managers stayed with Sinegal, embedding Sol Price's principles even more firmly in the Costco culture. People tend not to leave the company; the average tenure of store managers is 15 years. (Three senior Costco managers worked together in their youth at the same Fed-Mart in San Diego; three others were colleagues at an Anaheim Fed-Mart.) The axioms Costco lives by come straight from the House of Sol:

AXIOM NO. 1: Obey the law. When Fed-Mart began, according to Price, competitors sicced government inspectors on him, trying to find illegalities. As a matter of survival, he had to be purer than Caesar's wife. But then he came to believe it was good business. Retailers have many temptations to give zoning officials bribes, to give buyers kickbacks, and to finesse health and safety requirements. None of that benefits customers or employees, and none of it was tolerated by Price or Sinegal.

AXIOM NO. 2: Take care of your customers. Sure, every retailer says that, but Sol Price made clear to everyone under him that he meant it. "You are the fiduciary of the customer. You've got to give before you get. If you get something for a lower price, you pass on the savings."

AXIOM NO. 3: Take care of your employees. Sol Price actually invited unions in to represent Fed-Mart and Price Club workers. Following suit, Costco pays the top wage in retail, starting employees at $10 an hour. In the minds of Price and Sinegal, high wages yield high productivity, low turnover--Costco's is a third of the retail industry average of 64%, according to the National Retail Foundation--and minimal shrinkage; that's retail-speak for theft, which at Costco is about 13% of the industry norm.

AXIOM NO. 4: Practice the intelligent loss of sales. Many retailers' shelves are crowded with a plethora of products: different brands, different sizes, many choices. Costco offers relatively few choices. That means some customers may pass up purchases, because the gallon jar of mayonnaise is too big or the brand isn't their favorite. But the benefits far exceed the lost sales. Stocking fewer items streamlines distribution and hastens inventory turns--and nine out of ten customers are perfectly happy with the mayonnaise.

There are plenty more where those came from (see box), but you get the idea: Costco is driven by principles and ethics that you probably thought went the way of the five-and-dime. Sinegal reinforces them by traveling 200 days a year, trying to visit every store twice annually. He's got energy that leaves people half his age floundering in his wake. (Must be the near-daily racquetball games.) He doesn't inspect the troops; he interrogates them. CFO Richard Galanti, who sometimes goes along, recites the typical Sinegal rat-a-tat to store managers: "What's hot? What's Sam's beating us on? Have you seen that item in Best Buy? Don't you think we should have that?" All the while Sinegal scribbles notes that, upon his return to headquarters, will become the basis of memos and more questions that he will fire off in all directions.

Once a month Sinegal brings the troops to him for budget meetings, where 70 top managers hear again (and again) about the importance of exercising tight controls, getting the details right, and adhering to the Costco credo. But unlike in any corporate budget meeting known to man, a Costco manager can be upbraided by Sinegal for doing too well. Fresh-foods buyer Jeff Lyons dreads the next session because of a problem he has created by having no problems. Lyons makes an allowance each month for produce spoilage. Because he had hardly any in October, he widened his profit margin by one-half percentage point. "Our margin goal is 10%, and there'd better be a very good reason you did better than that," Lyons explains. "Otherwise Jim will say, 'Well, why didn't you lower prices?'"

Sinegal manages to be demanding without being intimidating. His bare-bones office helps set the tone for that style. So does his open-collared shirt and the nametag he wears, like everyone else. Not that he needs one. To walk with Sinegal from his headquarters building to the Costco next door is to hear a nonstop chorus of "Hi, Jim .... Hi, Jim .... Hi, Jim." He returns the greetings by using first names, without appearing to consult nametags. Sinegal has also kept himself in the good graces of subordinates by limiting his pay. His $350,000 salary last year was practically cause for drumming him out of the FORTUNE 500 CEO club; and at his own request, he took no bonus for the third consecutive year. He does have $16.5 million worth of options, but he's intent on capping his salary and bonus at about twice the level of a Costco store manager.

Sinegal is careful not to lop off managers' heads for taking chances, because, he says, "The art form of our business is intuition." Costco buyers have to take big chances. A warehouse stocks less than 10% of the items of a typical Wal-Mart, so buyers can't spread their bets around. If a high-end product doesn't move fast, it leaves a lot of money tied up in inventory. Bill Prescott, the chief buyer for consumer electronics, makes some of the toughest judgments about when new products are affordable enough and hot enough to be put on the Costco floor. He sensed the time had come for plasma TVs earlier this year, when the price fell below $5,000. He placed his order and held his breath. "You take an educated gamble," he says. "If you don't occasionally make a mistake, you're not doing your job." The TVs turned out to be a hit. "Our customers don't drive 15 miles to save on a jar of peanut butter," says Sinegal. "They come for the treasure hunt."

Because Costco does such large volume and has such good demographics, it's gone from being shunned by prestigious consumer-goods makers to being wooed by them. At first Titleist, Cuisinart, and Levi's wouldn't sell to Costco because they didn't want to displease their full-price retail customers or degrade their products in the discount channel. Things have changed dramatically in the past couple of years as the research has sunk in. Of all U.S. retail channels, according to A.C. Nielsen, the warehouse clubs attract the largest proportion of affluent shoppers, who account for 54% of their traffic. And the biggest attraction among them is Costco, whose members, Nielsen says, average 11.4 visits a year, at $94 a pop. The numbers at Sam's Club are 8.5 visits and $78, respectively.

While Costco innovates, Sam's tends to imitate. Costco began selling fresh meat and produce in 1986, Sam's in 1989. Costco introduced a premium private-label line called Kirkland Signature in 1995; Sam's version--Members Mark--came along in 1998. Costco started selling gasoline in 1995, Sam's Club in 1997. But while imitation may be the sincerest form of flattery, it shouldn't be confused with strategy. "By looking at what Costco did and trying to emulate it, Sam's didn't carve out its own unique strategy," says Michael Clayman, editor of the trade newsletter Warehouse Club Focus. And at least one of the "me too" moves made things worse. Soon after Costco and Price Club merged in 1993, Sam's bulked up by purchasing Pace warehouse clubs from Kmart. Many of the 91 stores were marginal operations in marginal locations. Analysts say that Sam's Club management became distracted as it tried to integrate the Pace stores into its system.

Within the past year Sam's Club has basically been folded into Wal-Mart. Among other things, that means its buyers are working in tandem with Wal-Mart buyers and are getting better deals, a strategy that has reduced purchasing costs, enabled Sam's to lower prices--and forced Costco to do so as well. Sam's has also joined Wal-Mart in championing a new inventory-tracking technology called RFID, for radio frequency identification (see "Wal-Mart Keeps the Change," on fortune.com). That will further lower distribution costs and raise efficiency. Sam's recently opened its first four stores in Canada, serving notice that Costco, which has 61 stores there, faces a north-of-the-border challenge.

All of which elicits this thought from Jim Sinegal: Bring 'em on. He loves keeping his troops in "a state of healthy paranoia," and there's no better motivational tool than telling them the superpower's missiles are aimed at them. "We've succeeded by being a moving target, by hitting them where they ain't," says Sinegal. "We need constant reminders to keep us on our game. I say at our management conferences that the amount Wal-Mart grows in just one year is the equivalent of Costco's size."

That said, it's hard to imagine Sam's eating Costco's lunch. The leopard can't change its spots, or its customers, overnight. Though Sam's is adding more upscale merchandise, like $2,000 jewelry, it's unlikely to draw hordes of "new luxury" seekers away from Costco, where membership renewal remains a strong 86%. And getting too tony risks alienating its current customers.

Pity poor Wal-Mart (a sentence I never thought I'd write). In this one niche, it's run up against a company that shows you can't discount some old business verities: The nimble first mover can outrun the powerful colossus; the innovator can stay a jump ahead of the imitator; the quality of leadership can trump the quantity of resources. "Here's the difference between Sam's and Costco," says Charlie Munger. "We have a live Sam Walton who's still there, and Wal-Mart doesn't."

FEEDBACK jhelyar@fortunemail.com