In August 2010, Cheryl Lenkowsky, an auditor for the Texas state comptroller, sent a letter to a top tax executive at Amazon.com’s Seattle headquarters. At that point, Amazon had been selling a wide array of merchandise to Texans for 15 years without collecting a penny of sales tax from them. Tax-free shopping was a delight for customers, a vital competitive edge for the company — and a hemorrhaging wound for state government.

Now, Lenkowsky informed the company, all that was about to end. Texas’s audit, which had gone back four years, had resulted in an “adjustment”: a bill for uncollected taxes, plus penalties and interest — $ 268,809,246.36 in all. Added Lenkowsky helpfully: “We have included a pre-addressed envelope for your payment convenience.”

Amazon responded fiercely. It appealed the assessment. It sued the comptroller for her audit records. It lobbied Rick Perry, Texas’s business-friendly governor. Most of all, Amazon insisted it had no “physical presence” in Texas — the basis for the tax claim — despite owning and operating a 630,800-square-foot distribution center (with an Amazon.com flag in front of it) in a Dallas suburb. When all that didn’t work, the company shuttered the facility and threw its 119 employees out of work, vowing to abandon the Lone Star State.

“In this world,” Benjamin Franklin famously wrote, “nothing can be said to be certain, except death and taxes.” Since its birth, Amazon has labored mightily to defy one part of this maxim, placing itself at the forefront of an epic battle now playing out across the country. At issue is a seemingly simple question: whether Amazon — and Internet companies like it, such as Overstock and Blue Nile — should have to gather sales taxes from all their customers, just as Sears, Costco, and, say, the Peoria Camera Shop have done for decades.

There’s a lot at stake. For state and local governments: an estimated $11.4 billion a year in desperately needed cash for streets, schools, police, and parks. For Amazon and archcompetitors like Wal-Mart: the struggle for retail primacy. For American consumers: what they pay and how they shop.

This story shows how the long, brutal war to force Internet retailers to collect taxes is finally being won. This saga of money, power, and commerce also provides a window into the way Amazon, which generated $61 billion in revenues last year, does business. Beneath its well-earned reputation for being customer-friendly — featuring a brilliant, affably cackling founder whom Fortune declared “Businessperson of the Year” in 2012 — the company is a brass-knuckled battler for every penny of competitive advantage. It’s no exaggeration to say you can’t fully appreciate the rise of Amazon without understanding this fight.

For 15 years the company refused to collect in most of the country, vowing to forever resist “illegal” efforts by the states. New alliances and strategies among its megarivals dramatically altered the debate, and in May the U.S. Senate passed legislation that would close the loophole for good. Its prospects for becoming law appear promising.

That’s an ignominious defeat for Amazon, right? Not so fast. The longtime foe of Internet levies actually supports the Senate bill (and now insists the issue never really mattered much anyway). It’s not the company’s first shift in strategy. One element, however, has remained constant: Amazon has shrewdly and successfully maneuvered to turn each development, good or bad, to its own advantage.

The war over Internet sales taxes has its origins in the late 1980s, when Amazon.com was barely a twinkle in Jeff Bezos’s eye. Back then it was mail-order houses that were winning business — and diverting money from government coffers — because they were allowed to sell tax-free in states where they lacked a store, sales agents, or any other sort of physical presence.

Then, as now, shoppers were legally obligated to “self-report” — to pay tax to their state on their own, even when out-of-state merchants didn’t collect it from them. But as a practical matter, almost no one did. So states were eager to bring a test case that would force the out-of-state businesses to collect.

The tax men zeroed in on the Quill Corp. Although its headquarters were in Illinois, Quill was a major purveyor of office equipment in North Dakota. In 1988 the state demanded that the company begin collecting its 5% levy on purchases by North Dakota residents.

Quill decided to fight instead, and it prevailed in a landmark 1992 U.S. Supreme Court case. Forcing distant sellers to capture sales tax for thousands of local jurisdictions would be so burdensome that it violates the Constitution’s commerce clause, the court ruled. A company is obliged to collect from shoppers only if it has a substantial physical presence in their state.

The term it used for that physical presence — “nexus” — would come to embody the entire debate, even as it shifted to Amazon and online retailers. “Nexus” would loom ever larger, with states pushing hard to prove companies had it — and Amazon fighting even harder to deny it.

Among the creation fables of America’s greatest enterprises, the issue of taxes doesn’t usually play a central role. But it’s integral to the founding of Amazon. When the company began selling books over the Internet in July 1995, three years after the Quill decision, exploiting the sales-tax loophole was very much on its founder’s mind. In an interview with Fast Company a year later, Bezos said he’d recognized that “physical location is very important for the success of a virtual business.” He based Amazon in Seattle partly to maximize the tax advantage.

“[I]t had to be in a small state,” explained Bezos, a libertarian who once donated $100,000 to defeat a proposed Washington state income tax on affluent residents. “In the mail-order business, you have to charge sales tax to customers who live in any state where you have a business presence. It made no sense for us to be in California or New York … I even investigated whether we could set up Amazon.com on an Indian reservation near San Francisco. This way we could have access to talent without all the tax consequences.” Alas, that wasn’t legally possible.

Low prices, along with convenience and huge selection, were a critical part of Amazon’s appeal. Allowing customers to dodge state and local sales tax amounts to a pricing advantage of as much as 10% — a huge edge in the world of razor-thin retail profit margins.

From early on, Amazon fought to keep its advantage. In 1997, when Barnes & Noble also began selling books tax-free online, Amazon howled. At the time, Barnes & Noble was the industry gorilla, with 1,000 stores; it had driven scores of independent booksellers out of business and was eager to crush the online upstart. Stung by Amazon’s marketing boast that it operated “Earth’s Biggest Bookstore,” Barnes & Noble had sued Amazon for “false and deceptive” ads.

The lawsuit was settled, but only after Amazon had countered in court that Barnes & Noble, by not collecting tax on Internet sales, was exploiting an “unfair method of competition.” Barnes & Noble got away with this by setting up its online business as an ostensibly independent enterprise, using a legal tactic known as “entity isolation.”

Other traditional retailers (including Wal-Mart and Target) would also employ this approach for several years before recognizing that it wasn’t legally sustainable and didn’t make business sense for them. They moved instead to a “bricks-and-clicks” strategy, cross-promoting their physical sites and online business, while allowing customers to pick up and return Internet orders at stores. “If you were playing the nexus game, you couldn’t do that,” says Warren Townsend, senior director of specialty tax for Wal-Mart. By 2003 virtually all the national chains were harvesting sales tax from online customers.

This left the competitive advantage of tax-free shopping exclusively in the hands of the online-only companies. Amazon would eagerly embrace the entity-isolation strategy, just as it was expanding at an astounding pace — into electronics and toys, cameras and beauty products, jewelry and barbecue grills — and becoming a threat to every retailer on the planet.

For state tax departments, the stakes were high. Sales tax represents about a third of total revenues in the 45 states that have such levies. But the states were too timid to act on their own. They decided to band together and form a national group called the Streamlined Sales Tax Project. The goal was to radically simplify the “burdensome” sales-tax system, then persuade Congress to pass a law allowing them to force all out-of-state businesses to collect. In 2000, the tax authorities set out to impose uniformity on the sales-tax codes of 45 states.

But the “Streamlined” process turned out to be anything but. Work-group sessions droned on for hours over arcane details. Should pencil leads be classified as tax-exempt school supplies? Is a beverage with less than 50% fruit juice taxable as a soft drink? An entire five-page white paper was prepared on the definition of candy. Businesses, invited to participate in hopes of adding lobbying muscle, began larding the agreement with provisions to benefit their private interests. For its part, Amazon squabbled with eBay over which companies (based on size of revenues) would be subject to the new rules, adding yet another impediment to a consensus.

The first draft of the Streamlined agreement was completed in November 2002, but it has been amended 28 times since. The document (with attached interpretive opinions) now runs to 204 pages. Yet only 24 states have signed on. The biggest states refused, unwilling to cede sovereignty. After more than a decade, the states were no closer to closing the Internet sales loophole than when they’d started. The effort had failed.

Throughout this time, Amazon insisted that it welcomed a “federal solution” requiring every company to collect. But it was clear that effort was going nowhere. With no consensus on Streamlined, congressional bills to overturn Quill had been repeatedly introduced and failed to make their way out of committee. By all accounts — except its own — Amazon did little in Washington to aid the federal effort. “They hid behind the skirt of this Streamlined group for 15 years,” charges Barnes & Noble CEO William Lynch. “Part of the strategy was to delay and pacify.”

Indeed, as Streamlined was turning into a quagmire, Amazon was going to extreme lengths — demanding, wheedling, suing, threatening, and negotiating — to avoid collecting for as long as possible, in as many states as possible.

It wouldn’t be a stretch to think of Paul Misener as Jeff Bezos’s political alter ego. Both earned a degree in electrical engineering from Princeton (just one year apart), and both display a certain earnest, geeky enthusiasm. While Bezos worked on Wall Street before founding Amazon, Misener became a lawyer in Washington, D.C., where he developed an appropriately nerdy hobby, amassing some 1,500 antique books and documents. (Misener certainly differs from the shaven-pated Bezos in one respect: He’s got a mane of silver — just short of a corporate mullet — with a distinctive river of white coursing left of center.)

As vice president for global public policy, Misener, 50, is Bezos’s field general in the long campaign against Internet taxes. With his cheerful demeanor and gleaming smile, Misener conveys the impression that what cynics might view as resisting taxes is in fact a noble quest to spread jobs and opportunity. Who could be against that? Indeed, Amazon says it’s driven strictly by principle. “Far from an e-commerce loophole,” Misener testified in Congress last August, “the constitutional limitation on states’ authority to collect sales tax is at the core of our nation’s founding principles.” As Misener puts it in an interview with Fortune, “We feel very good about our position because it’s a constitutional right.” (Bezos declined to be interviewed.)

Misener’s marching orders were clear from the outset. In 2000, the year Amazon hired him, Bezos — like many dotcom CEOs — voiced horror at the very notion of “taxing the Internet,” warning that it would smother a toddler of an industry. In later years, he would argue it was “not fair” that Amazon should have to collect taxes where it lacked a physical presence because “we’re not actually benefiting from any services that those states provide locally.” Never mind that it was only customers who would pay the taxes (and those customers do benefit from state services) — or that startups in other industries have always had to collect on their sales.

In 2008 — a point at which annual e-commerce had soared to $2.5 trillion — Bezos complained that local tax collection was so “horrendously complicated” that it imposed “an undue burden” on his company.

“Burden” doesn’t seem like quite the right word. Not only was Amazon able to master the challenge by 2008 — it had actually launched a service that was collecting sales tax for 2,500 merchants that used its website, including Macy’s and Target.

Misener acknowledges that the “too-burdensome” premise of the Quill decision hasn’t been valid for years. Yet Amazon has refused to start collecting because Quill says it doesn’t have to, according to Misener. “We don’t want to give up a constitutional right. There is a way to get at this collection question, which is for Congress to act.”

While clinging to Quill’s outdated protections, Amazon simultaneously sidestepped its dictates. Here’s where the entity-isolation strategy comes in. To avoid collecting taxes, Amazon placed fulfillment centers — each as big as 20 football fields — in separate legal subsidiaries (owned by Amazon.com, needless to say). Through this arrangement, the company argues, its warehouses don’t constitute a “physical presence.”

By 2008, Amazon had bricks and mortar — mostly distribution centers — in 17 sales-tax states. Yet it collected in only four: Washington, Kansas, Kentucky, and North Dakota. Among the places Amazon didn’t collect: Pennsylvania, Nevada, Arizona, and Texas, all states where it had warehouses.

State tax administrators declined to lift a finger against the company. Indiana went even further. To lure an Amazon warehouse in 2007, public officials there cut a special deal to exempt the company from collecting the state’s 7% sales tax. Amazon now has five warehouses in Indiana, where it has also received more than $11 million in economic development incentives.

Misener says his company’s fulfillment centers don’t constitute a physical presence because they have nothing more than a “brother-sister relationship” with Amazon’s retail business. “We don’t believe we have nexus,” says Misener.

Tax experts view the situation differently. University of Georgia law professor Walter Hellerstein, co-author of a leading textbook on state taxation, calls Amazon’s entity-isolation strategy “very, very aggressive.” Agrees University of Arizona tax law professor John Swain: “Amazon is trying to dress up their warehouses as if they are an independent vendor. It just doesn’t pass the smell test.” Contends Charles McLure, a former deputy assistant U.S. Treasury secretary and senior fellow emeritus at Stanford’s Hoover Institution: Amazon is “aiding and abetting tax evasion.”

The failure of Streamlined made it the bureaucratic equivalent of those notorious World War I battles in which massive, entrenched armies shed blood for months just to gain a few feet of territory. Ironically, though, it was a single state tax official whose actions eventually turned the entire conflict in a decisive new direction.

Robert Plattner, 62, never had any faith in Streamlined. As an influential private tax lawyer in Albany, N.Y., he had condemned the Quill decision as “a blunder of major proportions.” He dismissed prospects for a congressional solution and urged public officials to pursue a “Plan B.” In 2007, Plattner became New York State’s deputy commissioner for tax policy and soon hatched his own Plan B.

Amazon, of course, was the biggest target. But the company didn’t have a single warehouse in the state. So Plattner targeted its New York “affiliate” network: thousands of small businesses, bloggers, and nonprofits that link to Amazon.com on their websites in return for a commission on any resulting sales. New York would define these affiliates as de facto sales agents, establishing the company’s physical presence in the state. Voilà: instant nexus!

This “Amazon law,” which applied to other Internet retailers as well, took effect in April 2008. (Amazon immediately sued to overturn it.) Halfway across the country, a Dallas Morning News reporter named Maria Halkias took note of Amazon’s complaint that it didn’t need to collect in New York because it didn’t even have a warehouse there. Halkias recalled that she’d once received an Amazon package from a Texas address — as it turned out, a warehouse in Irving, near the Dallas/Fort Worth airport. Why, then, wasn’t Amazon collecting from Texas customers?

The site was hardly a secret. Amazon had noted its Texas presence in SEC filings, and local papers had excitedly reported on the warehouse’s arrival. Yet an official with the Texas comptroller’s office told Halkias that the state hadn’t known that Amazon had a Texas location. The agency dispatched an audit team to investigate.

As New York and Texas began bearing down, Amazon was engaging in contortions to avoid giving any opening to recession-ravaged states. “The economic outlook for many states is bleak,” advised one confidential 2010 memo to the Amazon Services LLC North American Retail Group, which surfaced in unrelated litigation. “As a result, states are pursuing taxpayers more aggressively than before. Amazon’s recent public experiences with New York and Texas provide timely and pertinent examples of the heightened risk. That’s why our attention to nexus-related issues are [sic] more important than ever.”

The company imposed an extraordinary set of rules restricting employees’ travel and activities. Travel, the memo warned, “could create sales tax nexus … which could expose our business to significant tax costs.”

The memo included a set of color-coded U.S. maps. Green and yellow states had the fewest restrictions. Travel to orange states required “preclearance” from the tax department, which tracked cumulative travel days for each state “to try to prevent the creation of a tax nexus.” Travel to red states was permitted only in “very limited circumstances.”

Once they arrived, employees who were allowed to attend industry meetings were instructed to avoid “soliciting or promoting the sale of products or services” as well as “speaking engagements, presentations, or other high-visibility activities” without advance approval. They were even barred from blogging while out of state.

Amazon — the company that contended that a 600,000-square-foot warehouse with more than 100 employees didn’t count as a “presence” — seemingly feared that much more tenuous links would create the dreaded nexus. Even writing promotional material for the company’s website on a freelance basis from a home in Texas was too much. A well-regarded longtime contractor named Betsy Danheim was dropped, an Amazon supervisor named Paul Hart explained in a March 2008 e-mail to his work team. The reason? “Turns out,” Hart wrote, “it could create a tax nexus issue.”

By 2009 it had become clear to brick-and-mortar stalwarts like Sears, Walgreen, and Wal-Mart that no solution was coming from Streamlined. Some of Amazon’s biggest rivals began to realize the time had come when they would need to enter the fray and take on the company.

Amazon was continuing to grab market share, across more and more product lines. As a purveyor of big-ticket goods, Best Buy was among those being hurt the worst. For a customer buying a $1,800 big-screen television package, saving $180 by dodging the sales tax had considerable appeal.

Best Buy started approaching other chains and retail trade associations to build urgency. “We just saw this gridlock,” says Laura Bishop, vice president for government relations at Best Buy. “We said, ‘Look, we should start crafting a more aggressive approach.’ ”

The big retailers were impressed by New York’s success in challenging Amazon. They began girding for state-by-state combat. Fresh ammunition was available from a 2009 study by three University of Tennessee professors; it projected how much each individual state was losing to the tax-free Internet. In 2010 alone, California was projected to lose $1.4 billion; Texas, $658 million. By 2012, according to the study, the total annual loss to state budgets would reach $11.4 billion.

But interviews with focus groups revealed no particular sympathy for strapped state governments. It was far better to cast the issue as a matter of fairness between traditional stores and online retail. The merchants’ rallying cry became “level the playing field” — a notion even free-market conservatives could embrace. Why should a downtown shop — which paid local taxes, provided local jobs, and supported Little League baseball and the Lions Club — face a 10% disadvantage competing with a big out-of-state corporation?

The retailers established an advocacy group called the Alliance for Main Street Fairness, with affiliates in different states. As its frontmen, the alliance tapped sympathetic local shopkeepers — the very mom-and-pops that Wal-Mart, Best Buy, and Barnes & Noble had made an endangered species. In 2011, Main Street Fairness began pressing states to crack down.

Amazon counterattacked. In each of the five states that enacted New York-style “Amazon laws” over the next two years, the company terminated its relationship with all local affiliates, cutting off income for thousands. This erased the legal basis for forcing it to collect. Amazon blamed the states, telling the former affiliates to complain to their lawmakers.

When Colorado passed a law requiring online retailers merely to advise customers that they might owe tax (and report shopper purchases to the state), Amazon fired its affiliates there, too, and said it wouldn’t bring them back until the law was repealed. That prompted Michael Mazerov, senior fellow with the Washington, D.C.-based Center on Budget and Policy Priorities, to accuse Amazon of “corporate hostage-taking.”

About the same time, Amazon had begun to rethink its distribution strategy. The company had always served big states like New York with warehouses located elsewhere. But its customer base was soaring, and Bezos was moving to develop the capacity for next-day — or even same-day — delivery. This required many more distribution centers, much closer to customers. The demands of Amazon’s evolving business model were encroaching on its ability to base decisions on tax avoidance.

As its political position grew less tenable, Amazon started maneuvering to combine its needs (more warehouses) with its wants (preserving tax-free shopping for as long as possible). This strategy played out first in South Carolina. In late 2010 the company struck a deal with outgoing governor Mark Sanford, who promised Amazon an exemption from gathering sales tax (along with tens of millions of dollars in traditional inducements) in return for a new distribution center with 1,250 jobs. But that agreement required approval from the state legislature.

The Alliance for Main Street Fairness rushed in to raise a stink, holding press conferences, issuing statements, and running newspaper and TV ads. Business lobbyists buttonholed legislators, demanding that Amazon start collecting sales tax immediately. Opponents wore T-shirts reading STAND WITH MAIN STREET.

Amazon finally offered a compromise: It would start capturing sales tax in January 2016 — almost five years later. When the South Carolina House overwhelmingly rejected that, Amazon announced that it was taking its jobs elsewhere and abandoning its half-built warehouse. “The 1,200 jobs and nearly $100 million in capital investment that were coming to the state — aren’t,” Amazon’s Misener declared at a press conference.

The announcement had the desired effect. Three weeks later, the legislature flip-flopped — and the retailer announced it was returning to South Carolina after all, with its exemption until 2016. Score one for Amazon.

As a dozen states, pressured by America’s biggest retailers, suddenly began debating their own steps to squeeze Amazon, California and Texas loomed as the largest battlegrounds. California didn’t have a single Amazon warehouse. Yet there had been efforts to make online sellers collect the state’s 7.25% sales tax for more than a decade. They’d been led by independent booksellers, who came to see themselves as the canaries in the mineshaft in sensing the threat that Amazon posed to brick-and-mortar businesses.

To make their case that Amazon had nexus, the booksellers had focused on a half-dozen California offices the company leased for several small software businesses it had bought, as well as Lab126, the Cupertino research-and-development shop that developed the Kindle. But the state’s tax-collection board rejected the idea that this represented a “physical presence,” and two different governors had vetoed bills pushed by the booksellers to broaden the nexus rules in ways that would cover Amazon.

“We were trying to get Wal-Mart, Target, Best Buy, Home Depot onboard for years,” says Hut Landon, executive director of the Northern California Independent Booksellers Association. “Amazon was kicking their butt. But they didn’t want to get involved. We couldn’t do it on our own. Politically, we just didn’t have the influence and the power. We needed the big guys.”

In 2011, for the first time, the booksellers found the California Retailers Association and its megacorporation members marching beside them. With fresh muscle, and California mired in deficits, a new bill to broaden the nexus rules sailed through the legislature and was signed into law by Gov. Jerry Brown in June 2011. Amazon immediately terminated its 10,000 affiliates in California, urging them to besiege legislators. When that didn’t work, the company put up $5 million to launch a statewide referendum to overturn the measure.

The Alliance for Main Street Fairness countered with its own campaign, which included political-style attack ads. The organization’s website urged citizens to anonymously “Drop a dime on Amazon,” because “Amazon.com will do and say anything to maintain an unfair advantage over Main Street businesses.” The traditional retailers vowed to spend whatever it took to uphold the law. Says Lenny Goldberg, lobbyist for the booksellers: “We were looking at this as the battle of the titans.”

Misener had vowed never to concede in California. But the momentum had shifted. Amazon finally relented, and the two sides hammered out a bargain. The company would start collecting sales tax in California after about a year, on Sept. 15, 2012, and the state would get three Amazon warehouses.

As Texas state comptroller Susan Combs sees it, the states that gave Amazon extended safe harbors on sales-tax collection are “chumps.” As she puts it, “It’s flat-out wrong!” At 6-foot-2, Combs, 68, cuts a bold figure. Raised on a West Texas cattle ranch, she was educated at Vassar and the University of Texas Law School, then worked as a prosecutor in Dallas and published a romance novel. A Republican, she’s been in Texas politics for 20 years, the last seven as the state’s independently elected tax collector.

Combs proudly claims bragging rights for having gotten Amazon to start corralling sales tax faster than anyone. But it required some high-dollar horse-trading.

In the fall of 2010, after Combs’ auditors presented Amazon with the $269 million bill for back taxes, the company insisted it had no physical presence in Texas, citing the ownership of its local warehouse by an “independent subsidiary” called Amazon.com.kydc. Combs found this laughable. Reaching into her Amazon file, she plucks out a photo of the sprawling building and slides it toward me. “When they have a sign out front that says AMAZON.COM, that was pretty clear,” she says. “They tied everything back to Seattle. They didn’t call themselves Fred’s Distribution Center. They called themselves Amazon.com.”

Combs pulls out a copy of a 1963 Texas law expanding tax-capturing requirements to “any retailer maintaining, occupying, or using, permanently or temporarily, directly or indirectly, or through a subsidiary, or agent by whatever name called, an office, place of distribution … warehouse or storage place.” As Combs puts it, “When the statute is as clear as I think this one is, you need to pay up!”

Amazon certainly didn’t think so. When it got Combs’ $269 million tax bill, it scotched plans to build a second Texas distribution center. Then, in February 2011, Amazon announced it was pulling out of Texas altogether, shutting down the Irving warehouse and terminating all of its workers there. An Amazon executive explained that the company needed to leave because of Texas’s “unfavorable regulatory climate.” (Chief Executive magazine has named Texas as America’s most business-friendly state for nine straight years.)

By this time, the Main Street Alliance had arrived on the scene, offering support for Combs and backing a bill to tighten the state’s basis for forcing Amazon to collect. When the Texas Retailers Association held its annual “Retail Roundup” lobbying day in Austin, Best Buy swarmed the Capitol with 20 blue-shirted store managers.

The legislature passed the Amazon bill, but Gov. Perry vetoed it. As it moved forward again in a special session, Amazon offered a South Carolina-style bargain: It would build massive new warehouses in Texas, providing 6,000 jobs, in return for a sales-tax exemption until January 2016 — 4½ years. Bolstered by the big-box lobbyists, the lawmakers stood their ground, tucking the measure into a veto-proof “fiscal matters” bill, before adjourning their special session in June 2011.

“We all had a nice Texas summer,” says Combs. “Then we got a call eventually in the spring from some folks wanting to come talk turkey.” At about 2 p.m. on April 13, 2012, Paul Misener arrived at the comptroller’s office in Austin. Misener is a tall man. “I wore really good heels, which was smart,” recalls Combs. “Because I needed to be eye to eye.” The deal was struck in 30 minutes. Amazon would start collecting Texas’s 8.25% sales tax on July 1, 2012 — just two months later. The company would, of course, build distribution centers, pledging to invest $200 million and create at least 2,500 jobs in Texas over the next four years.

Combs wrote off Amazon’s $269 million tax bill, reasoning that it was most crucial to get Amazon collecting quickly. Amazon did make what it later described as “an immaterial payment” to the state. “The key thing was to get certainty,” Combs says. “I absolutely believe we did the right thing. We got what we think is the best deal in the country.”

Amazon, as usual, got a good deal too. Says Misener: “We’re very happy to be in Texas, creating new jobs and investment.”

Amazon denies that its deals in states such as Texas represent any kind of reversal. According to Misener, the company has struck tax-collection agreements merely because it wanted to expand its distribution network and was eager to avoid conflict. “We decided we wanted to go only to places that truly welcomed us,” he says.

But there’s no question that the past two years have represented a tipping point. This Christmas, Amazon will be collecting taxes in 13 states; by January 2016 it will be assessing tax in 17 states, covering about half the U.S. population. The company has now agreed to reap sales tax in every state where it operates a warehouse. In New York, it has lost its challenges to the original “Amazon law.” New York officials say that since the law’s passage in 2008, they have received $508 million in extra sales tax collected by 35 online businesses.

Even as it has reluctantly begun to yield this competitive edge, Amazon has minimized its impact, saying the company does just fine, thank you, even where it collects. Amazon has less need for the advantage than it once did; millions of consumers now treat the site as a utility, using it as a default option for a huge array of purchases. Still, academic studies suggest that the addition of sales tax drives 10% or more of customers to shop elsewhere. Where Amazon has begun adding tax to bills, Barnes & Noble and Best Buy both claim significant upticks in their business.

Pressure from the big-box stores has also had the desired effect in Washington. The Marketplace Fairness Act passed the U.S. Senate in May, with broad bipartisan support and the backing of President Obama. The bill would allow states to force collection, with no need to prove nexus. Advocates give it a fifty-fifty chance of passing in the House.

Among the corporate giants backing the bill: Wal-Mart, Home Depot, Best Buy — and Amazon, which is actively lobbying in Washington after years of tepid engagement. Amazon has retained a powerhouse D.C. lobbying firm and now has two former U.S. senators, Trent Lott and John Breaux, promoting the bill’s passage.

In a Senate hearing last fall, South Carolina Republican Jim DeMint (who has since left Congress) accused Amazon of backing the legislation to avoid giving online competitors the advantage it long enjoyed. “Now that you’re going to have to pay taxes in all of these states where you have a physical presence,” DeMint told Misener, “you want to come back and tax these other companies that don’t.”

Misener insisted that his company favors the measure simply to “level the playing field for all sellers” — embracing the battle cry of the company’s opponents. If the Marketplace Fairness Act passes, it would supersede Amazon’s negotiated agreements, moving up the dates of required collection in a few states.

The long, nasty history has been put aside as erstwhile enemies awkwardly unite. “There was bloodlust between Amazon and all the people in this coalition,” says Jason Brewer, spokesman for the Retail Industry Leaders Association. “At this point, we’re trying gracefully to row in the same direction.”

Now it is a different online giant — eBay — that is leading the opposition, issuing its own call to arms in the name of small business (online business, that is), even though the legislation exempts any company with annual Internet sales of less than $1 million.

Meanwhile, Amazon, as promised, has been rapidly building new distribution centers across the country, including three in Texas. There, Amazon is making the most of its beefed-up presence in the state. It is, of course, happily exploiting millions in economic-development incentives.

But that isn’t all. Under Texas law, the pint-size suburbs that will house new Amazon warehouses may enjoy a special windfall: They can receive a portion of the sales tax on all products shipped from that warehouse to Texas customers. In gratitude, all three municipalities have already agreed to “rebate” varying amounts — as much as 85% in one case — to Amazon. This bonanza would run well into the millions. After years of scorched-earth battles to avoid collecting sales tax, Amazon has managed to find a way to channel a chunk of that money — which comes out of its customers’ pockets — into its own coffers.

This story is from the June 10, 2013 issue of Fortune.