Following the 1995 season head coach Don Shula announced his retirement from coaching, having spent 26 straight seasons with the Dolphins. Jimmy Johnson, quit Dallas after winning Super Bowls XXVII and XXVIII, was hired as only the third head coach in Dolphins history.
Johnson and the Dolphins endured a rough season, winning their first three games before losing two straight. On October 27 the Dolphins hosted the Cowboys with both teams 4–3 in one of the most anticipated games of the regular season; the Cowboys rallied and won handily 29–10, and Cowboys coach Barry Switzer declared that no Dolphins player (even quarterback Dan Marino) could start on his Cowboys squad. The Dolphins won twice in the next two weeks but then lost three straight, ending any playoff hopes despite winning their final two games and finishing 8–8.