In May 1995, several Texas sports teams, including the Houston Rockets, proposed legislation that would dedicate state tax revenue to build new arenas. Although the bill was failed in the Texas House of Representatives, Rockets owner Leslie Alexander announced he would continue to study the possibility of constructing a new arena in downtown Houston, saying the 20-year-old Summit arena was too outdated to be profitable. Although the Summit's management said they could renovate the building for a small part of the cost of a new arena, the Rockets began talks with the city of Houston on a possible location for an arena, They also negotiated with Houston Aeros and Summit owner, Chuck Watson, to release them from their contract with the Summit, which ran until 2003.

As the negotiations continued into 1996, a panel appointed by Houston mayor Bob Lanier reported that building a new arena was "essential to keep pro sports in Houston". After Watson rejected a contract buyout proposal of $30 million, the Rockets filed a legal challenge against their lease, stating the "need to be able to buy out" of the lease. However, the city of Houston filed a counterclaim to force the Rockets to stay at the Summit, saying that if the Rockets did not honor their contract, then they might "have no incentive to honor any new agreement with the city of Houston to play in a new downtown sports arena". The validity of the lease was eventually upheld, and in April 1997, Lanier announced that the Rockets and Watson would have to agree to share control of the new arena equally, or lose access to it altogether. After both parties agreed to the terms, a bill that authorized increased taxes to pay for a new arena was signed into law in July, by then-Governor George W. Bush.

However, after the NHL decided not to consider Houston as a location for an expansion team because of the indecision over the new arena, Lanier said that he would not have a referendum in November. The Rockets began an appeal in January 1998 against the court order to stay at the Summit, but then dropped it in May, because they felt that a new arena would be ready by the time they finished their lease. In January 1999, recently elected mayor Lee Brown guaranteed a referendum on the issue before the end of the year. After several months negotiating with the Harris County-Houston Sports Authority, the Rockets finalized a deal to pay half of the constructions costs, and a referendum was set for November 2. The deal was approved by Brown and the Houston City Council, but Watson started an opposition group against the referendum, saying the arena was "not in Houston's interest". On November 3, the results of the referendum were announced, and the arena proposal was rejected by 54% of voters. Alexander said "we never thought we would lose" and that they were "devastated by the loss".

After the vote, NBA commissioner David Stern said "if there's not a new building...I think it's certain that the team will be relocated." The Houston Sports Authority had not planned to meet with the Rockets until after the 1999–2000 NBA season ended, but after the Rockets began to talk to other cities about relocation, they resumed talks in February 2000. Although the Rockets continued to negotiate with Louisville, Kentucky, a funding plan for the arena in Houston was released in June. A final agreement was proposed on July 6, and both the Rockets and mayor Brown agreed to the terms. After the city council approved the deal, the proposal was placed on the November referendum ballot. Leading up to the vote, the Rockets stressed that there would be "no new taxes of any kind", although opponents said the new arena would raise energy consumption, and also contended that the public would pay for too much of the costs of the arena. Contributions for the campaign for the arena included donations of US$400,000 from Reliant Energy, and a total of $590,000 in loans and contributions from Enron and Ken Lay, who the Rockets said was a "tireless" force in the campaign. On November 8, the arena was approved by 66% of voters.

🏟️