Grayson speelde voor onder meer Leeds United (1988-1992), – in het bijzonder – Leicester City (1992-1997), Aston Villa (1997-1999) en Blackburn Rovers (1999-2002). Met al deze clubs kwam hij uit op het hoogste niveau, de Premier League. Leeds United werd Engels landskampioen in 1992. Grayson was er lang bij, maar vertrok op 13 maart 1992 naar Leicester City en mocht geen medaille in ontvangst nemen. Met Leicester versloeg hij Middlesbrough in de finale van de League Cup van 1997, na het spelen van een replay.[2] Hij werd toen door de fans uitgeroepen tot speler van het jaar.[3] In 2006 beëindigde hij zijn loopbaan bij Blackpool, waar hij sinds 2005 speler-coach was.[4]
In 2008 werd hij trainer van Leeds United, waar hij zijn spelersloopbaan was begonnen in 1988. Blackpool wilde hem en Leeds voor het gerecht dagen omdat de overgang tijdens het seizoen werd doorgevoerd.[5] Als speler van Leeds haalde hij slechts twee competitiewedstrijden, maar als trainer had hij meer succes. Onder zijn leiding promoveerde Leeds in 2010 naar de Championship, na een tijd in – naar de normen van de club – het moeras van de League One te hebben vertoefd.[6] In 2012 werd hij ontslagen en werd dan vier jaar trainer van Preston North End, van 2013 tot 2017. Aansluitend werd hij aangesteld als coach van Sunderland.[7] Sinds 6 juli 2019 was Grayson opnieuw aan de slag als trainer van Blackpool. Op 12 februari 2020 werd Grayson de laan uitgestuurd nadat de club slechts één wedstrijd op twaalf won.[8]