Although Palace were the better side in the first half they crumbled after the break and goals from David Nugent and Kelvin Wilson ensured cup progress for Paul Simpson's outfit.
The visitors conceded nine corners in the first half but Peter Taylor's Eagles failed to capitalise on them.
In the first minute Michael Ricketts made a crucial clearance to snatch the ball off Clinton Morrison and was injured in the process.
After treatment Ricketts limped back onto the field and it was a good job for Preston he did as he was soon called upon again to defend as he cleared Mark Hudson's header off the line.
Immediately play switched to the other end and Ricketts, now in his striker's role, fired wide. But the best chance of the first half fell to Carl Fletcher on 15 minutes.
Another Palace corner from Mark Kennedy fell perfectly onto the head of Fletcher but the Palace skipper couldn't keep his effort down and the ball whistled over the bar.
Preston weren't doing much attacking, but Paul McKenna did miss a useful opportunity on 20 minutes only to place his shot wide of the post.
David Nugent was having a quiet first half by his standards but nonetheless was credited with Preston's first shot on target which arrived on 30 minutes with Scott Flinders making a routine save.
Although Palace were passing the ball impressively, penetration into the last third was not a frequent event.
James Scowcroft and Morrison combined well but Scowcroft eventually mis-hit his shot and Andy Lonergan managed to save at the second attempt.
The second half exploded into action with Nugent immediately making an impact.
The Preston hit-man picked up a loose ball on the left-hand side and moved into Palace's penalty area.
Darren Ward hesitated and failed to make a tackle but even so Hudson was still favourite to get to the ball first.
However, he lost out as Nugent finished the move he had begun with a cracking shot from 10 yards out that flew past Flinders.
That goal came on 46 minutes but, within a couple of minutes, Stuart Green gave Palace hope of an immediate reply when he burst through the centre of Preston's defence.
He unleashed a tremendous right-foot shot which Lonergan did exceptionally well to turn away for a corner.
Lonergan had to make another excellent save, this time diverting a 20-yard shot from Fletcher after Preston were able to only half-clear Matt Lawrence's deep cross from the left.
Substitute Paul Ifill fired wide before Kelvin Wilson wrapped up the tie eight minutes from time. Flinders was badly at fault when he failed to make a simple catch from Lewis Neal's corner on the left-hand side.
From the loose ball central defender Wilson was offered a gift just two yards out and he made no mistake although the ball did take a slight deflection off Hudson.
Palace just fell apart after that and the disgruntled fans made for the exit and so did Peter Taylor's side - out of the FA Cup.