The Reds were given a hard time as Iain Dowie's men fought for their lives and Johnson's header gave the Eagles a vital win which was deserved for their effort alone, as they worked their socks off.
Indeed Liverpool had to wait 70 minutes for their first real shot on target. Although they put Palace under extreme pressure in the final 15 minutes or so, the home backline, in particular Tony Popovic and Fitz Hall were outstanding.
Milan Baros took the brunt of a few late tackles early on and eventually had to retire before the break.
Even so this was a poor performance by Liverpool's standards, as perhaps they had their eye on the Champions League semi-final against Chelsea.
Palace took full advantage with a relentless display that ended a run of five games without a victory.
The first half was played at a fast pace with Palace allowing the visitors little space.
While the Reds enjoyed plenty of possession in the middle of the park the Eagles kept to Iain Dowie's tight game-plan, as he used five across midfield and left Johnson as the lone man up front.
Liverpool were unable to break down the system to the extent that Gabor Kiraly had no more to do than make a routine stop from Djimi Traore midway through the first half.
Palace, urged on by the prompting and probing of skipper Michael Hughes, caused a couple of anxious moments for visiting keeper Jerzy Dudek.
First he tipped over Popovic's close-range header from Hughes' free-kick, before having to realign to collect a shot from Danny Granville.
Wayne Routledge caused problems to the Liverpool rearguard who often got caught out by the acceleration of the young Palace winger.
It was from Routledge's effort that Palace went in front 11 minutes before the break.
The Reds had more than one chance to clear their lines, but neither Jamie Carragher nor Steve Finnan were able to get the ball away and instead it dropped to Routledge five yards outside the area.
The winger struck it on the half-volley. It was meant as a shot and was going wide but Johnson reacted like a flash to get his head to it and the ball flew past Dudek and nestled neatly into the left corner.
After the break Palace began at a cracking pace as Johnson beat the offside trap on the right side and crossed low into the box. As the ball bounced past two Liverpool defenders Tom Soares, at the far post, was left with a simple chance but the young midfielder delayed and mis-controlled, allowing the defence to clear for a corner.
Hughes' volley from 20 yards flew a whisker past the post before the nerves set in and Liverpool finally began to impose themselves on the game.
Djibril Cisse came off the bench and made a big difference while fellow substitute Darren Potter created the visitors' fist serious shot on target, but Kiraly saved well.
Cisse showed his pace as he opened up the home defence, but again Kiraly was equal to the shot.
Palace defended in numbers as Liverpool plugged away and launched attack after attack. Steven Gerrard saw a header saved by Kiraly, who then made the save of the afternoon to once again deny the hardworking Gerrard.
The England midfielder struck the ball well from 15 yards out but the Hungarian keeper made a sensational diving stop to keep it out.
As Palace held on, Carragher had once last chance but the England defender fired over the bar.
The home fans breathed a sigh of relief and within moments three precious points were theirs.