Parkinson was tien jaar profvoetballer en begon zijn loopbaan bij Wigan Athletic, waarvoor hij meer dan 100 wedstrijden heeft gespeeld. In 1993 speelde hij even voor Bournemouth, waar hij eveneens een vaste waarde was.[3] Van 1993 tot 1999 stond hij onder contract bij Everton. Toen hij zijn contract tekende, had Everton geen trainer. Succescoach Howard Kendall was weg en Mike Walker was nog niet gearriveerd. Parkinson was tot en met 1997 een bepalende speler bij The Toffees. In 1995 won hij de FA Cup met Everton tegen Manchester United.[4] Een doelpunt van Paul Rideout volstond voor de mannen van trainer Joe Royle, hoewel Manchester United het zonder zijn geschorste aanvaller Éric Cantona moest stellen (karatetrap).[5] Een knieblessure verstoorde in 1997 de verdere plannen van Parkinson, die niet herstelde.
Parkinson, die de finale van de FA Cup tegen Manchester United mocht starten – als beloning voor goede prestaties toen de vaste kracht John Ebbrell geschorst was – kondigde in december 1999 zijn voetbalpensioen aan op amper 28-jarige leeftijd.[6] In 2000, een jaar na zijn afscheid, kreeg hij van Everton een testimonial tegen Manchester City.[7][8]