Alan Shearer reacted quickly to a Robert free-kick and slotted the ball home to equalise on 13 minutes. The Magpies went ahead on 15 minutes when Carl Cort was able to flick on a Robert cross.
Newcastle's attacking football flowed, but defensive errors let Niclas Alexandersson in to equalise on 34 minutes. He was able to muscle Sylvain Distin off the ball to slot the ball past Given.
Nicos Dabizas had a bullet header saved by Simonsen on the line, and Newcastle had plenty of other chances to go back in the lead before half-time.
The Toon Army had to wait until 59 minutes to see their team take the lead once more, Andy O'Brien managed to scramble the ball over the line from a messy corner. From then on Newcastle were hardly troubled by Everton, and they had plenty of chances to extend their lead.
They did so on 71 minutes through Nolberto Solano when Kieron Dyer went past three defenders and crossed the ball for Solano to slot home. Solano doubled his tally two minutes later when he was fed through by a clever pass from Jenas.
A double substitution saw Lomana Lua Lua replacing Cort, and Olivier Bernard replacing Laurent Robert. The two substitutes combined on 88 to score Newcastle's sixth. Lua Lua sped past returning Geordie Steve Watson, and slid through a perfect pass for Bernard to slot home.
Newcastle cemented their fourth place in the Premiership with an impressive attacking display, but defensive errors showed that this is the area that still needs strengthening. Newcastle have tuesday's trip to Villa Park to look forward to and possibly the return of Craig Bellamy.