Pochettino lifted to new heights after taking charge in 2014, leading them to a second-place finish in the Premier League in 2016-17.
That was the second of four consecutive top-four finishes, meaning Spurs became a regular Champions League fixture on his watch and were beaten finalists in Europe's top competition last season, losing 2-0 to Liverpool in Madrid.
However, a run that featured incredibly dramatic quarter-final and semi-final triumphs over Manchester City and Ajax respectively served to distract from dwindling domestic form that has not picked up this term.
A laboured 1-1 draw against Sheffield United before the international break left Spurs 14th in the table, with three wins and 14 points from 12 top-flight matches.
"We were extremely reluctant to make this change and it is not a decision the board has taken lightly, nor in haste," said Tottenham chairman Daniel Levy in a statement that confirmed coaches Jesus Perez, Miguel D'Agostino and Antoni Jimenez would also leave the club.
"Regrettably domestic results at the end of last season and beginning of this season have been extremely disappointing.
"It falls to the board to make the difficult decisions - this one made more so given the many memorable moments we have had with Mauricio and his coaching staff - but we do so in the club's best interests.
18 - No ever-present Premier League club has lost more games in all competitions during 2019 than Tottenham Hotspur have under Mauricio Pochettino (18). Dismissed. pic.twitter.com/Qmg8pCy47a
— OptaJoe (@OptaJoe) November 19, 2019
"Mauricio and his coaching staff will always be part of our history. I have the utmost admiration for the manner in which he dealt with the difficult times away from a home ground whilst we built the new stadium and for the warmth and positivity he brought to us.
"I should like to thank him and his coaching staff for all they have contributed. They will always be welcome here.
"We have a talented squad. We need to re-energise and look to deliver a positive season for our supporters."
Pochettino's success at Spurs came despite long periods of inactivity in the transfer market and more than a season-and-a-half as tenants at Wembley for home games as their new stadium was built.
Uncertainty over the future of some key first-team stars has lingered over their poor form this season, which arguably reached its lowest point when Bayern Munich subjected them to a 7-2 Champions League defeat at the Tottenham Hotspur Stadium.
Christian Eriksen, Toby Alderweireld and Jan Vertonghen are all out of contract in June 2020 and, despite belatedly getting high-quality additions in the form of Giovani Lo Celso and club-record signing Tanguy Ndombele, Pochettino was seemingly unable to wring any further excellence from a core squad that has been around for the majority of his tenure.
The struggles are of recent months are unlikely to affect Pochettino's stock in the game, with Real Madrid, Manchester United and Bayern having all been touted as his next possible destinations.
Ex-Chelsea and Manchester United boss Jose Mourinho is the early favourite to succeed Pochettino with bookmakers, who also consider Rafael Benitez, Carlo Ancelotti, Eddie Howe, Julian Nagelsmann and Massimiliano Allegri to be in the running.
Photo Getty Images Caption: Mauricio Pochettino manager sacked by Spurs