Nick Chadwick has now hit four goals for Chester in seven games
Gregg Blundell's second penalty in as many games and a late header from Nick Chadwick helped earn Chester only their second league win of the season.
Blundell was twice involved in the night's key incident, being brought down in the box by Gateshead defender James Curtis, who was sent off.
He then fired home from the spot, only for on-loan striker Mike Mackay to drill home Gateshead's equaliser.
But Chadwick won the points for City, nodding home Neil Ashton's cross.
The victory will give Chester's young side confidence in their thankless task of trying to beat the drop to the Blue Square North.
But their main battle remains off the pitch as they appeal against their 15-point pre-season points deduction, the second of their two punishments totalling 25 points for going into administration following relegation from the Football League.
Chester now have nine points from seven games, leaving them on -16, but having narrowed the gap to 19 points on 23rd-placed Forest Green.
Gateshead were the first to threaten, Christoph Ascherl firing over the bar from 20 yards, before Curtis tested City keeper John Danby with a header.
But Curtis was then given a straight red for bringing down Blundell, who picked himself up to convert the penalty.
Recalled midfielder Ben Wilkinson and Chadwick both went close to doubling the lead as the hosts sought to press home their numerical advantage.
But Gateshead refused to lie down, levelling six minutes after the interval when Mackay latched onto Ascherl's pass before slotting a left-footed shot past Danby.
Kevin Roberts and Chadwick both spurned opportunities to put the hosts back in front, while Blundell saw a header saved by Jim Provett.
But the hosts got a deserved winner with 14 minutes remaining when summer signing Chadwick got on the end of Ashton's right-wing cross to register his fourth goal of the season.
E-mail this to a friend 
Printable version 
Bookmark with:
What are these?