Danny Bloomfield has had moments when he cannot buy a goal, but a timely first half brace propelled the Linnets into the second round.
The Walks outfit played as well in the opening half as they have this season.
Manager Tommy Taylor said: "I was very pleased with our first half display and we should have been out of sight by the break.
"After the break our midfield lacked the balance it did in the first period and we were too narrow.
"We left too much space down the flanks which allowed Gloucester to get into our box."
And although they faded as City desperately tried to force their way back into the tie, Lynn recorded their first clean sheet and win since Ludlow seven weeks ago in the FA Cup.
New non-contract signing from Leicestershire side Oadby Town, Nick Matthews, slotted straight in at centre-back with Danny Hammond.
Matthews (19) was on Leicester City's youth books, then Lynn pounced when Boston Utd did not follow up their interest in him.
With new boss Taylor's presence already being felt, he moved Ryan Clarke into midfield, and it paid off as he and Carl Holmes (on the right) had outstanding first halves.
Taylor said: "The new lad came in and done well. He just needed the first 10 minutes to settle.
"Ryan Clarke gave us a lot more energy in midfield alongside Cammy in the first period and I took him off because he'd run himself into the ground.
"I thought his appetite was spot on and he was very sharp in the tackle."
With Mark Angel and Craig Fishlock missing, Chris Bacon gained only his second start of the season.
"I decided to play Staffy wide left to give the boy Bacon a chance," added Taylor.
"He did well in the first half but ran out of steam in the second half."
Bloomfield gave himself and his team early confidence with a tenth-minute goal.
Clarke and Adam Jones combined on the right for the latter to cross for Bloomfield to lose his marker and slam past the keeper.
Bacon had great chances on 15 and 20 minutes, the first blazing over when Bloomfield was tackled by Lyndon Tomkins and the ball ran across goal; the second when heading over as Jones and David Staff interchanged passes.
In the 34th minute the hosts' first effort on target saw Mark Camm nod Wilkinson's header off the line, and Staff cleared up to Bloomfield, who bagged his second goal from a few yards out.
Keeper Matt Bath saved brilliantly from Staff, Bloomfield was twice denied a hat-trick and then Bath saved with his feet from Holmes dead on half-time.
Tigers player-boss Chris Burns sent himself and Jimmy Cox on at the interval and City piled on the pressure, aided by Lynn giving the ball away.
But with skipper Gary Setchell ably leading his troops the Linnets stood up well, and all Gloucester could muster was Steve Wilson saving with his legs from Daryl Addis during one of seven second half corners, while Wilkinson headed into Wilson's arms in injury time.
Lynn had even more chances at the end for their three subs.
Robbie Harris' shot was blocked, Jack Defty headed into Bath's arms and Lee Stevenson should have done better from close range.
City: Bath, Smith, M. Thompson (Burns h-t), Griffiths, Tomkins, C. Thompson, Mustoe (Knight 65), Webb, Addis, Davis (Cox h-t), Wilkinson. Subs not used: Harris.
Lynn: Wilson, Jones, Setchell, Matthews, Hammond, Camm, Clarke (Defty 80), Holmes (Harris 66), Bacon, Bloomfield (Stevenson 71), Staff. Subs not used: Blake, Higgs.
Goals: Bloomfield 10, 34. Booked: Jones 85 (time-wasting).
Referee: Les Sinclair (Brierly Hill). Attendance: 383.