Playing in the First Qualifying round for the first time since 1985, the Rebels swarmed all over the luckless Spartan (Greene King) League outfit and could easily have finished with a score in double-figures.
Tommy Langley led the charge with another two goals to bring his tally to three in two matches and the signs are that he is starting to meet the vast expectations placed on him by the impatient Slough crowd
But the most eye-catching performance was that of transfer-listed midfielder Brian Greenaway. Called into replace the injured Mark Adams, Greenaway turned in one of his best ever performances in a Slough shirt and during the first-half was at the centre of everything.
It was from his corner in the 15th minute that the Rebels snatched the lead, Jeff Bateman nodding the ball back for the unmarked Langley to steer past 'keeper Bob McLean.
And Greenaway provided the cross from which Tony Dell scored his first Slough goal nine minutes later, guiding it inside the post from 12-yards.
Bateman, Langley and Neal Stanley all went close before the Rebels scored their third goal four minutes after the half-time break.
Langley showed good close control on the bye-line to swing in a cross for Stanley to head in at the far post for his fourth goal of the season.
Slough exposed Walthamstow's weakness in the air again in the 68th minute when Langley flicked Bateman's drilled cross past the flat-footed McLean.
Player assistant-manager Trevor How completed the rout in the 85th minute. Walthamstow couldn't clear Robbie Johnson's free-kick and Stanley turned the ball back across the penatly-area for How to raise above the defence and knock in number five.
The only blot on the Rebels copybook came sixty seconds later when a lapse in concentration allowed Ali Sylvester to pull back a consolation goal.
Walthamstow Pennant Line up
McLean, Wood, Brennan, Springer, Sylvester, Stevenson, Carter, Roche, Scawthorn, Edwards, Goodman. Subs: Petruccio, Worf (for Wood, Stevenson).