Jahren – unterbrochen nur durch eine kurze Ausleihphase beim FC Darlington, für Middlesbrough absolvieren. Unter der Regentschaft von Trainer Bruce Rioch entwickelte sich der für seine Größe überdurchschnittlich technisch begabte, kopfballstarke und schnelle Pallister nach zwei Aufstiegen in Serie von der drittklassigen Third Division in die erstklassige First Division in den Jahren 1987 und 1988 an der Seite seines Innenverteidigerpartners Tony Mowbray zu einem der besten englischen Abwehrspieler seiner Zeit. Am 27. April 1988 gab er zudem bei einem Auswärtsspiel gegen Ungarn seinen Einstand in der englischen Nationalmannschaft. Für England sollte er bis 1996 insgesamt 22 Länderspiele bestreiten, kam jedoch während keines großen Turniers zum Einsatz. Kurz nachdem der Verein nach einer Saison wieder in die Second Division absteigen musste, wechselte er für die damalige Rekordablösesumme in Großbritannien von 2,3 Millionen Pfund zu Manchester United.

In Manchester wurde er nach Anlaufschwierigkeiten, bei denen die hohe Transfersumme eine hohe Belastung für Pallister zu sein schien, immer mehr zu einer festen Größe in der Mannschaft und gewann auf Anhieb 1990 mit dem FA Cup seine erste Trophäe, die zudem den Beginn einer äußerst erfolgreichen Ära des Vereins begründete. Im anschließenden Jahr errang er mit dem Europapokal der Pokalsieger – nach dem 2:1-Finalsieg gegen den FC Barcelona – einen bedeutenden europäischen Vereinstitel, dem sogar noch der Supercup folgte. In seiner Zeit bei Manchester, in der er zumeist mit Steve Bruce in der Innenverteidigung spielte, gewann er neben den bereits erwähnten Titel mit vier Meisterschaften, zwei weiteren FA Cups und einem Ligapokal insgesamt zehn bedeutende Trophäen, was lange Zeit einen Rekord darstellte, bis ihn Denis Irwin übertraf. Außerdem wurde er 1992 von der Profispielervereinigung „Professional Footballers' Association“ (PFA) zu Englands Fußballer des Jahres gewählt.

Pallister beendete seine Zeit in Manchester mit einer Vizemeisterschaft in der Saison 1997/98 und musste sich dabei dem FC Arsenal nur mit einem Punkt Rückstand geschlagen geben. Für 2,5 Millionen Pfund wechselte er dann zu seinem früheren Verein FC Middlesbrough zurück, wo mittlerweile sein ehemaliger Manchester Mannschaftskamerad Bryan Robson das Traineramt ausübte. Dort verbrachte er seine letzten drei Jahre als Fußballspieler und kam auf 55 Meisterschaftsspiele.

Seit seinem Rücktritt vom aktiven Sport ist Pallister häufig als Fußballexperte im englischen Fernsehen zu sehen.