Chris Greenacre and Gareth Taylor each got two goals for Rovers, one in each half, as after leading 3-0, Tranmere were pulled back to 3-2 before Greenacre rounded off the win.
Ronnie Moore made just one change to the side which defeated Millwall eight days ago, with Jason McAteer replacing the suspended Chris Shuker in midfield for Tranmere, as John Mullin moved to the right. Craig Curran made the bench for the first time, where he was joined by Achterberg, Harrison, Tremarco and Jones.
It was the Conference side who started best in horrible windy conditions at Prenton Park, with Carl Murray seeing his deflected shot fall onto the roof ot Gavin Ward's goal after nine minutes.
However, from then on Tranmere dominated the first half, with Woking barely getting into the Rovers half of the field, let alone having a shot.
First Chris Greenacre flashed a cross across the six-yard box, before Steve Davies, again playing on the left-wing, headed just over the bar.
After Murray had sent a free-kick over the bar for Woking, Davies saw his well struck shot saved by goalkeeper Jalal when Rovers had had strong appeals for a penalty turned down.
From the resulting corner though, Rovers took the lead. From Paul McLaren's corner (yes, the man who Ronnie Moore described as a dead-ball specialist finally took a set-piece), Gareth Taylor headed past Jalal to put Tranmere ahead.
On 28-minutes, Taylor could and should have had a second for Tranmere, but the striker headed the ball away from goal from Davies' pinpoint cross.
Minutes later, Taylor produced a fantastic save out of Jalal, which saw most of the ground and the referee applauding the Woking 'keeper. From Mullin's knock down, Taylor vollied the ball towards goal, but Jalal stuck out an arm and tipped the ball over.
It was another Davies cross that produced Rovers' second goal after 38 minutes. The youngster flew past the Woking right-back on the left before whipping in a low cross which Chris Greenacre flicked over the goalkeeper into the roof of the net past 'keeper Jalal to make it 2-0 at half-time.
Two minutes after half-time, Tranmere continued from where they left the game at half-time, with Greenacre producing another fine save out of the Woking shot-stopper.
However, Taylor got his second of the game and fifth for Tranmere just minutes later, as his diving header hit the back of the net from John Mullin's cross.
The goal put Tranmere 3-0 up, and considering that Tranmere had not lost in the three previous games in which Gareth Taylor had scored for them, things were looking rosey.
The next real action of the game wasn't until the 57-minute mark, with Craig McAllister providing some interest with a header and McLaren shooting wide after 10 minutes or so without any action.
Four minutes later, Woking turned the game on it's head, with a goal for Simon Jackson, who's cross from the Woking left was carried by the wind and ended up in the net having trickled through Gavin Ward's legs.
After eight more second half minutes, Woking were well and truelly back in the game, as McAllister scored the Cards second goal of the game. After poor defending and an awful clearence from Shane Sherriff, the ball fell to McAllister on the edge of the area, who picked his spot and fired passed Ward into the bottom right-hand corner.
With Woking still in the game, Davies brought another save out of Jalal and then Mike Jones got his first appearence of the season and just his second for Tranmere as he replaced Paul McLaren and moved to right-midfield.
On 83-minutes, Tranmere finally secured the win, with Chris Greenacre netting his second of the game. Shane Sherriff knocked the ball down to the former Stoke striker from Davies' corner, and Greenacre vollied into put Tranmere 4-2 up.
Each 'keeper was forced into one more save before time was up, with Ward saving well low down from El-Salahi and then Mike Jones forcing Jalal into one more save.
Rovers were relieved when the final whistle finally went after three minutes of injury time, with both teams were given a standing ovation off the pitch by the Tranmere fans.
In all, the first half was a quality performance by Tranmere, but in the second half Ronnie Moore's men switched off and should they do this against a better team, as they did against Huddersfield, they would not have won.
The second round draw is at half-time of the Bury vs. Weymouth game, live on the BBC tomorrow. It should start around 3:00
Jones' Man Of The Match: Steve Davies was brilliant in the first half but was less involved in the second, but Gareth Taylor was quality through-out, showing just how much of a difference he makes to the team. Tranmere have still not lost when he has scored.