Pallister's transfer broke the national record for a fee paid for a defender, as well as being the highest fee between British clubs, and the second highest fee to be paid by a British club (second only to Ian Rush's return to Liverpool from Juventus a year earlier).
Pallister had the rare achievement of representing the English national side before appearing in the top flight; in 1988 when playing in the Second Division for Middlesbrough. Later that year he helped 'Boro win their second successive promotion and reach the First Division, just two years after they almost went out of business, but was unable to keep them there and they were relegated on the final day of the 1988–89 season. As one of the highest regarded defenders in England, his days at Ayresome Park were looking numbered as soon as Boro were relegated but he did begin the 1989–90 season still at the club in the Second Division before his move to United was completed.
Although it was his excellent defensive displays that helped Manchester United to the league title along with Steve Bruce at the heart of the defence, forming one of the best central defensive partnerships in the club's history, in the 1992–93 season, he scored a memorable goal in the final home game of the season against Blackburn Rovers. Into stoppage time, with his team winning 3–1, he stepped up to drive a free-kick into the bottom corner from the edge of the penalty area. It was his first goal of the season and just about summed up an incredible season for Manchester United. He partnered Bruce in central defence for virtually every game until Bruce left United to join Birmingham City on a free transfer at the end of the 1995–96 season. The following campaign saw Pallister partnered with either Bruce's former understudy David May or with new signing Ronny Johnsen, and ended with United winning their fourth league title in five seasons.
The final season Pallister played for Manchester United was the 1997–98 season in which Manchester United came second in the league table, losing by one point to Arsenal.
During his time at Manchester United, Pallister won the FA Cup in 1990, 1994 and 1996, UEFA Cup Winners' Cup in 1991, Football League Cup in 1992, Premier League title in 1993, 1994, 1996 and 1997. He was also part of the team that came second in the league in 1992, 1995 and 1998, as well as the team that finished runners-up in the League Cup in 1991 and 1994 and the FA Cup in 1995. By the time of his departure from Old Trafford after nine years, he was the only player to have collected winner's medals in all of the club's successes under Alex Ferguson's management, and second only to Brian McClair (who left United at the same time) he was the club's longest serving player.
He also scored some crucial goals for United. He scored an equaliser in extra time against Crystal Palace in the FA Cup semi-final at Villa Park, forcing a replay which United won and in which Pallister made the scoresheet once again. In April 1997, he scored twice against Liverpool in a match billed the "title decider" which ended in a 3–1 United win at Anfield. These would be the last two goals he scored for the club, who went on to win their fourth league title in four seasons shortly afterwards. His first goal for United had come on 12 November 1989, as he scored their only goal in the 1–0 home win over Nottingham Forest in the First Division.
Transferred back to Middlesbrough for £2.5million (actually more than he had cost United nine years earlier) in July 1998 (his departure from Old Trafford at least partly prompted by United's acquisition of Jaap Stam), he scored once against Southampton in 55 League appearances, as well as appearing in two FA Cup matches and four League Cup matches.
His final playing season, in which Middlesbrough finished 14th in the table, was season 2000–01. He was brought back to Teesside by manager Bryan Robson, who had played alongside Pallister at Old Trafford until 1994.
He retired from playing due to a succession of injuries on 4 July 2001, at the age of 36, just three weeks after the appointment of Steve McClaren as manager following the departure of Bryan Robson (his former Manchester United colleague).