At the same time, Adams again lobbied the city for a new stadium, one with club seating and other revenue generators present in recently–built NFL stadiums, and he committed to pay for 25% of the cost of a new stadium. However, mayor Bob Lanier initially supported Adams’s bid for a new stadium privately but refused to publicly support the project. Although Houstonians wanted to keep the Oilers, they were leery of investing more money on a stadium so soon after the Astrodome improvements. The city was also still struggling to recover from the oil collapse of the 1980s. Adams, sensing that he was not going to get the stadium he wanted, began shopping the Oilers to other cities. He was particularly intrigued by Nashville and opened secret talks with mayor Phil Bredesen. At the end of the 1995 season, Adams announced that the Oilers would be moving to Nashville for the 1998 season. City officials there promised to contribute $144 million toward a new stadium, as well as $70 million in ticket sales. At that point, support for the Oilers in the Houston area all but disappeared.

The 1996 season was a disaster for the Oilers; they played before crowds of fewer than 20,000 and games were so quiet that it was possible to hear conversations on the field from the grandstand. Meanwhile, the team’s radio network, which once stretched across the state, was reduced to the flagship station in Houston and a few affiliates in Tennessee. By October 1996 the flagship station (KTRH) was cutting off games prior to their finish in favor of the Houston Rockets pre-game show. The team went 8–8, finishing 6–2 in road games and only 2–6 in home games. Adams, the city, and the league were unwilling to see this continue for another season, so a deal was reached to let the Oilers out of their lease a year early and move to Tennessee.

In 1999, Robert McNair was awarded, at a cost of $1 billion, an expansion team that replaced the Oilers in Houston. The franchise became the Houston Texans, which adopted a similar red, white and blue team color tandem and inherited the sports complex the Oilers had played in, but not the Oilers’ former home; NRG Stadium would be built next door to the Astrodome in 2002.