After eight successive AFC Championship appearances, five of which the Patriots won, they fell by the wayside on wild card weekend.
Speculation has surrounded Brady's future and here, the PA news agency assesses what the future holds for arguably the sport's greatest ever quarterback.
What does Brady mean to the Patriots?
Brady, along with head coach Bill Belichick, has brought an era of unprecedented success to Massachusetts.
The pair have combined to win six Super Bowl titles since Brady, an unheralded sixth-round pick in the 2000 draft, was initially pressed into service in place of injured Patriots great Drew Bledsoe.
They have won the AFC East in 16 of his 19 seasons, reached 13 AFC Championship games and nine Super Bowls, while Brady's 85,750 passing yards and 614 touchdowns are NFL records for the regular season and play-offs combined. He is also a three-time NFL MVP and four-time Super Bowl MVP.
Why does this feel like the end?
Brady will turn 43 before next season starts and while there has been discussion of his long-term plans for some years, a host of factors have seen it multiply this time around.
On the field, the Patriots offence has been significantly below its previous standards, with the retirement of tight end Rob Gronkowski and the failed signings of troubled wide receivers Josh Gordon and Antonio Brown leaving Brady throwing to a below-par bunch of pass-catchers.
Offensive co-ordinator Josh McDaniels is once more a candidate for head-coaching vacancies around the league while off the field, Brady's contract was structured to void after this season and the mansion he owns with his supermodel wife Gisele Bundchen is up for sale. It was reduced in price during the season but would still set potential purchasers back 33.9million US dollars (£25.8million).
Brady said in his press conference after the Titans game that it was "pretty unlikely" he would retire but concluded a message to Patriots fans with: "Who knows what the future holds? We'll leave it at that."
Where could Brady go?
Were he to leave Foxborough, Brady would have no shortage of suitors and would surely look to move to a serious contender.
The Indianapolis Colts, long-time rivals of the Pats during Peyton Manning's tenure as their quarterback, were rocked by the pre-season retirement of Andrew Luck and – though ex-Patriot Jacoby Brissett held the fort admirably – Brady would instantly have their strong roster eyeing the Super Bowl.
The Denver Broncos have themselves struggled to replace Manning while their AFC West rivals the Raiders could welcome a high-profile upgrade on Derek Carr as they move from Oakland to Las Vegas.
The Los Angeles Chargers and New Orleans Saints have their own veteran franchise favourites, Philip Rivers and Drew Brees respectively, to consider while the Pittsburgh Steelers will monitor Ben Roethlisberger's recovery from injury.
The Tampa Bay Buccaneers, Carolina Panthers and Chicago Bears could be among the other teams involved in a wide-open quarterback market.