[3] In November 1990, after only 20 league games and 2 goals for Wimbledon and following an alleged training ground bust-up with Keith Curle, Gayle moved to Birmingham City for £175,000, helping the Blues to promotion in 1992.
A day after the end of his loan spell, on 13 September 1993, Gayle was back in the top flight, Coventry City paying £100,000 for his services.
This again proved to be only a short stay, Gayle making 14 league appearances and scoring 3 goals before moving to Stoke City for £70,000 on 23 January 1995.
He moved to Gillingham on loan on 14 March 1996, making 9 league appearances and scoring 3 goals which helped secure the club's promotion from Division Three.
On 14 December 2000, Gayle was released by Shrewsbury, joining a Torquay United side in need of a target man that up to that time under manager Wes Saunders they had never really had.
He made his Torquay league debut on 16 December 2000 against Hull City at Boothferry Park, a rare 2–1 away win for the Gulls, but injured his hamstring during the game and was out for the next month.