On November 14, 1994, Pardee was fired as head coach by the Oilers, and Fisher was promoted to replace him for the last five games of the season. Following the 1994 campaign, the Oilers drafted quarterback Steve McNair and decided to retain Fisher's services as head coach. The new coach did not disappoint, leading the team to a 7-9 record in 1995, tied for second place in the division. The following year, which saw the debut of Heisman Trophy winner Eddie George for the Oilers, they achieved an 8-8 record. However, an inability to get a new stadium deal in Houston caused owner Bud Adams to relocate the team to Tennessee for the 1997 season.
In the 1997 and 1998 seasons, the franchise was unable to break through the .500 plateau, going 8-8 both years. This led to criticism from fans that Fisher was incapable of ever achieving anything more. The 1999 season, which saw the renaming of the team to the Tennessee Titans, proved the doubters wrong, however, when Fisher led the Titans to a surprising 13-3 regular season record, leading them deep into the playoffs (thanks to the Music City Miracle) and all the way to Super Bowl XXXIV. Ranked among the greatest championship games of all-time, Fisher's team fell to the St. Louis Rams, 23-16, when wideout Kevin Dyson was tackled one yard short of the end zone with no time remaining. This play became known as "The Tackle" in football lore. Tennessee achieved the same record the next year, but were again defeated in the playoffs by an eventual world champion, this time, the Baltimore Ravens.
The 2001 season was a disappointing one for the Titans, as they could only muster a 7-9 showing. The beginning of the next season proved to be even worse, with the franchise starting off with a 1-4 record. Following one home loss, owner Bud Adams made the comment to reporters that perhaps the Titans "were getting outcoached". This provided a spark the team needed, and they finished the season with a 11-5 record and made it to the AFC Championship Game.
The 2003 season saw more success, with yet another trip to the playoffs and McNair winning the League Most Valuable Player award. Again, they lost to an eventual world champion, the New England Patriots, but the team's progress did not go unnoticed. The 2004 season, however, was plagued by injuries from the start, and Fisher's worst record as head coach (5-11) was the result. Following the season, many veteran players (such as Samari Rolle and Derrick Mason) were cut in an effort to comply with the strict salary cap. The relative youth of the team resulted in a disappointing 2005 season as well. Before the 2005 season, Fisher hired Norm Chow out of USC to be his offensive coordinator.
In 2006, the Titans finished a better-than-expected 8-8. The Tennessee Titans then exercized their right to extend his contract by a year, keeping him as the head coach through the 2007 season.
Throughout his tenure with the Tennessee Titans, Fisher has maintained a good relationship with his players, and is now almost universally known as "Coach Fish".