England striker Gary Lineker was the hero on August 26 1985 - the last time that Everton came away from Spurs with maximum points - and despite playing over an hour with 10 men they were the stronger team.
David Moyes decided to play Johnson up front on his own, leaving James Beattie on the bench, and the striker repaid his manager's faith by putting in a good performance.
Spurs boss Martin Jol again elected to play with Robbie Keane and Dimitar Berbatov up front leaving England striker Jermain Defoe kicking his heels on the bench.
The visitors started brightly and created the first chance, Leon Osman picked up the ball just outside the box, but his shot from 20 yards was too tame and wide to bother Spurs keeper Paul Robinson.
Tottenham kicked into life on 15 minutes when new Bulgarian striker Berbatov picked up the ball on the left-hand side, but his cross for Keane was well cleared by Joleon Lescott.
South Korean Young-Pyo Lee terrorised Everton midfielder Kevin Kilbane on the left-hand side and was shown a yellow card for a body check on the Spurs left-back after 16 minutes.
Minutes later came the best chance of the half. Teemu Tainio's throw-in on the left-hand side was acrobatically hooked towards the goal by Berbatov and Kilbane managed to hit the cross bar with his attempted clearance.
Calum Davenport came close as the home side started to mount pressure but headed wide from Keane's inswinging free-kick.
Everton were reduced to ten men when Kilbane received his second yellow card for a trip on Lee on the edge of the area.
The visitors ended the half in the same way in which they started it with Osman shooting wide from 18 yards.
The home side struggled to make the extra man count at the start of the second half and went behind shortly after the re-start.
Johnson ran at Benoit Assou-Ekotto, who brought him down on the right-hand side of the box. From the resulting free-kick Mikel Arteta's ball was met by an unmarked Lescott whose header was deflected into the goal by Davenport.
On 66 minutes Osman managed to hold off Edgar Davids to play the ball to Phil Neville and his cross was met by Johnson who scored his second goal of the season.
The introduction of Jermain Defoe in the second half was not enough for the home side to mount a come back, despite creating a number of half chances.
The visitors were difficult break down, despite playing a lot of the game a man down, and the defeat for Spurs means it is their worst start to a season for five years, while Everton continue their unbeaten run which is their best start since 2001.