However, after the arrival of new manager Mick McCarthy, Stephenson's first-team opportunities were limited and he found himself being loaned to Gillingham, for whom he made 12 league starts and scored two goals.
During his three seasons at Bootham Crescent, Stephenson established himself as York's first choice right winger and he made just under 100 appearances for the club, scoring five times.
Little reluctantly placed him on the transfer list along with several other first-team players in order to raise much-needed funds before his contract ran out.
Hartlepool, along with his former club Brentford, both made offers, but Little delayed the transfer in order to try and use the winger to help aid York's play-off bid.
York failed to make the play-offs, however, and Stephenson took the opportunity to move closer to his Newcastle roots and joined Hartlepool in March 1998.
He made his final appearance for Pools against Cheltenham Town in the play-off semi-final second leg, in which he missed a penalty in the deciding shootout.
Upon the arrival of new manager Glenn Roeder at Norwich, and his decision to build his own backroom staff, Stephenson was offered the job of first-team coach in early November 2007.
Despite some trouble with the Hartlepool chairman regarding compensation, Roeder was ultimately successful with the appointment, and Stephenson commenced work with the Canaries two months later.