Gateshead missed the chance to go top of Blue Square North as The Linnets turned in their best performance of the season at The Walks.
Lynn had some fortune, Matt Hocking's own-goal giving them the lead on 55 minutes, but their hard work made them well worth the lead.
Full-back Luke Graham got a second from Michael Frew's free kick on 83 minutes.
The result gives King's Lynn their first victory since November and leaves them 14th in the Blue Square North.
Manager Keith Webb said the win helped relax fears he may have had about losing his job following last weekend's defeat to Blyth Spartans.
"I was a little bit low last Saturday, as you could tell, today I thought the team went out and performed for the full 90 minutes," he told BBC Radio Norfolk.
"It was difficult to tell who was second in the table, we did everything right, it was as good a performance as we've put in this season," he said.
Lynn were boosted before kick-off with the return to the side of defender Mark Peters and Webb said he made all the difference.
"He's got all that experience, he's a leader, and it was the right time to put him in," said Webb
"People could have argued that he should have been in earlier but he wasn't fit enough and we've put him in at the right time, but there were a lot of leaders out there today," he said.
Bookmark with:
What are these?