Born in Plaistow in east London, Stimson played for the Essex county representative football team and was on the books of Queens Park Rangers, before joining Tottenham Hotspur on an apprenticeship in July 1984. A year later, he signed his first professional contract, at the age of 17. He made his Football League debut against Everton in May 1987, but struggled to gain a place in the first team, and was sent to Leyton Orient on loan in March 1988, where he played ten times. During the following season, he was loaned out again, this time to Gillingham, whose manager, Keith Burkinshaw, had worked with him at Tottenham. Stimson made 18 appearances for the Kent-based club and, although he was unable to help the team avoid relegation from the Third Division, his contribution impressed the fans, who voted him into second place in the club's player of the year ballot.