Three goals in the opening half hour take the Magpies top of the fledgling Premier League table.
Despite an encouraging pre-season, Lee's team looked like strangers as they were ripped apart by a Newcastle side that certainly can play better.
Bolton couldn't get any worse in the second half and they at least showed some fight.
But it was a demoralising result for Wanderers, desperate to put one over on their old manager.
"I think the occasion got to the players," admitted Lee who is expected to close another transfer deal in the next few days.
Nicolas Anelka showed why he's so highly-rated with a superbly struck consolation after Bolton's best move of the match.
And the arrival of El Hadji Diouf at half-time for the ineffective Ricardo Vaz Te also added some sparkle to the team.
But it was too late and Allardyce's side, with Alan Smith excellent in midfield and Obafemi Martins the ace predator, won comfortably.
Lee started without new wing men Christian Wilhelmsson and Daniel Braaten. There was no place either in his squad for Spaniard Ivan Campo or, crucially, injured Ivory Coast defender Abdoulaye Meite.
Michael Owen was missing for the Geordies, but latest recruit Cacapa made it to the bench.
And Newcastle, who failed to take a point off Wanderers last season, couldn't have scripted a better start against Bolton's makeshift defence.
The home side had a warning when JLloyd Samuel and Gerald Cid contrived to set-up Mark Viduka for a shot deflected for a corner.
But the reprieve didn't last long. Charles N'Zogbia curled in a free-kick that eluded defenders and attackers alike to end up in the back of Jussi Jaaskelainen's net after 11 minutes.
Ten minutes later it was 2-0 and again a cross exposed the home defence.
James Milner centred from the Newcastle left, the ball cleared Samuel eight yards out and landed for the unmarked Martins.
The former Inter Milan striker controlled in an instant and smashed in a brilliant overhead kick.
Bolton thought they'd won a penalty when Smith appeared to handle Gary Speed's goalbound shot.
Speed and Kevin Nolan chased after referee Foy who brushed aside their protests.
Almost immediately Newcastle attacked again. Martins spun away from his marker and fired home left-footed from 20 yards, albeit with a wicked deflection off Abdoulaye Faye.