A last-minute goal from half-time substitute Bryan Hughes sparked wild celebrations in what was a must-win victory for the home side.
They came from behind after trailing to a first-half penalty and took advantage of Villa being reduced to ten men after skipper Gareth Barry was sent off in the 59th minute with a straight red card for a professional foul.
Pardew's task of trying to keep Charlton in the Premiership was always going to be a difficult one and he said they needed to win half of their remaining matches to have a chance of survival.
In his first match in charge against Fulham on Wednesday, the Addicks were denied victory by a dodgy linesman's decision and it looked as though referee Rob Styles would be the villain of the piece in this match.
He awarded the visitors a disputed penalty when Hermann Hreidarsson was adjudged to have fouled Barry and the Villa captain scored from the spot, his ninth goal of the season and fifth from the penalty spot.
Earlier Villa keeper Gabor Kiraly had saved brilliantly to deflect a Darren Ambrose volley on to the crossbar before stopping a stinging effort by Darren Bent.
Charlton equalised in the 57th minute when Darren Bent scored his tenth goal of the season with a brilliantly placed diving header.
Two minutes later came Barry's sending off when he brought Dennis Rommedahl down just outside the area.
Charlton almost took the lead when Djimi Traore's header hit the bar and, from the resulting goalmouth scramble, Ambrose saw his shot cleared off the line.
With a minute to go, Villa almost snatched victory when Gabriel Agbonlahor shot wide, but play switched quickly to the other end and substitute Jerome Thomas curled in a cross which was headed on by Hreidarsson for Hughes to head home from close range.
It was the former Birmingham City man's first goal in 17 matches and left Villa without a win in nine games.