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.
The Dolphins raced to a 24-3 lead in the third quarter, scoring twice on Patriots fumbles, then withstood a Ben Coates touchdown catch to win 24-10, the first win for Jimmy Johnson as a coach since Super Bowl XXVIII.
The Dolphins picked off Cardinals quarterbacks Kent Graham and Boomer Esiason a total of three times as they exploded to 38 points, winning 38-10.
The slumping NY Jets erupted and the ensuing game became a slugfest. Aaron Glenn picked off Dan Marino at the Jets goalline and ran back a 100-yard touchdown. Webster Slaughter then caught a 30-yard touchdown, but after that the Dolphins exploded to five straight touchdowns, marred by poor kicking by Joe Nedney, who missed a point after and a field goal. The Jets rallied from down 33-14, highlighted by a 29-yard touchdown catch by Keyshawn Johnson on 4th and goal at the 29; Keyshawn outjumped the entire Dolphins defense for the catch. Nedney then put the game out of reach on a 29-yard field goal in the final minutes and the Dolphins won 36-27.
In a 10-6 loss Dan Marino suffered his fourth straight loss to the Colts (dating ironically to another 10-6 loss, this one in December 1994). He threw only eight passes for 67 yards before giving way to backup Bernie Kosar, who managed 122 yards but no touchdowns. The game saw only 467 total yards and eight quarterback sacks as Jim Harbaugh's one-yard score to Ken Dilger put the game's only touchdown on the board.
Marino had to sit out as Craig Erickson was sacked four times and intercepted once. The Dolphins fumbled seven times, losing two, mostly on botched snaps between Erickson and center Tim Ruddy. Seattle's John Friesz threw for 299 yards, 196 of them on three touchdowns, in a 22-15 Seahawks win.
With Marino still out Miami traveled to Rich Stadium having lost seventeen of their last 21 meetings with the Bills, but things turned around as the Bills reached the Miami 1-yard line down 14-7 but Terrell Buckley picked off Jim Kelly and ran back a 99-yard touchdown for the 21-7 Miami win. It was Kelly's third pick of the game to go with seven sacks; the disconsolate Kelly said after the game, "We deserved to be booed. I deserved to be booed."
In a penalty-laden game (a combined seventeen fouls for 149 yards) the Eagles and Dolphins traded touchdowns before the Eagles won 35-28. Craig Erickson had two touchdowns but one interception, and following a 49-yard Ricky Watters score Bernie Kosar was put into the game, throwing a touchdown to O.J. McDuffie.
It was the most anticipated regular-season meeting in the NFL of the year; Miami sports personality Dan Le Batard called it "the most anticipated meeting ever between two 4-3 teams." The game was the first meeting between former Cowboys coach Jimmy Johnson and the Cowboys since the tumultuous March 1994 showdown with Jerry Jones that ended Johnson's job as Cowboys head coach. With Michael Irvin back with the team after a league suspension for the first five games, the Cowboys broke out of a 10-9 Miami lead with three Troy Aikman touchdowns. After the 29-10 Cowboys win coach Barry Switzer stated no Miami starter, Dan Marino included, could start for his Cowboys squad.
The Dolphins fell 42-23 and their record sank to 4-5 as Dan Marino and Craig Erickson managed 331 passing yards to Drew Bledsoe's 419 yards. Miami got two touchdowns from Karim Abdul-Jabbar while Curtis Martin punched in three scores and Ben Coates caught two touchdowns, one a short pass caught at the New England 17 that he ran in for the 83-yard score.
Dan Marino passed 50,000 passing yards, the first player to do so, on a 37-yard strike to O.J. McDuffie as the Dolphins emphatically returned to .500 by whipping the Colts 37-13; the previous year Marino had broken Fran Tarkenton records for touchdowns, yardage, and completions in a home loss to the Patriots and a season sweep by the Colts. Jim Harbaugh managed only 126 yards and was sacked in the endzone for a safety.
In their final season in Houston the future Tennessee Titans clawed to a 17-13 lead in the fourth quarter. Zach Thomas intercepted Chris Chandler for a 26-yard touchdown but Chandler led the game-tying drive in the fourth on Al Del Greco's 33-yard field goal. Marino got the Dolphins down field in the final minute and Joe Nedney won the game 23-20 on a 29-yard kick. Both teams now stood at 6-5.
Despite two fumbles and a Mike Tomczak pick-six (run back by Calvin Jackson for a 61-yard touchdown) the Steelers erased a 14-3 Dolphins lead and won 24-17 on Ernie Mills' 20-yard score. The Dolphins were flagged for nine penalties to one for the Steelers.
The Dolphins traveled to Oakland–Alameda County Coliseum for the first time since November 1980; the Dolphins were winless there and fell again, this time 17-7 as Dan Marino was intercepted three times and managed only one touchdown.
For the second straight week the Dolphins fell 17-7, this time to the Giants, who picked off Marino twice as the two teams managed only 474 combined yards.
All but eliminated from the playoff race, the Dolphins salvaged a glimmer of hope as they clawed to a 16-7 lead in the fourth and absorbed a late Eric Moulds touchdown to win 16-14. The Dolphins rushed for 140 yards and the win put the Bills to the edge of falling out of the playoffs.
The disastrous Rich Kotite era in New York ended in the sixth game of 1996 where the Jets blew a halftime lead; up 14-7 after a Hugh Douglas fumble return score, the Jets saw the Dolphins outscore them 24-14 in the second half. Dan Marino threw for three touchdowns as Karim Abdul-Jabbar exploded to 152 yards on the ground, outclassing the 69 yards of Adrian Murrell. The Dolphins finished 8-8 while the Jets limped into the offseason at 1-15.