After Jamie Taylor missed a glorious chance to open the scoring in the opening 20 seconds, City's heads didn't drop and they went into the break a goal up with Nicky Nicolau firing in after Dan Gray saw his shot land and his colleague's trusty left boot.
Wrexham, who could easily have seen substitute Declan Walker sent off after pushing Taylor to the floor, failed to cope with the Imps' dominant play and the lead was deservedly doubled when Taylor curled home a superb effort 11 minutes after the break.
Teenager Conner Robinson got in on the act in the 69th minute, drilling home to make it 3-0 and although the hosts rallied with Jay Colbeck netting 10 minutes later, subsitute Colin Larkin restored the three-goal advantage with a cool finish from a Nicolau cross.
Nicolau came within inches of adding a fifth in the final minute when he saw his curling effort hit the post and although Wrexham responded with Joe Clarke reducing the arrears, the afternoon belonged to the Imps with the long-awaited first away success coming against one of the early season pace-setters.
Skipper Gary Mills and teenage striker Conner Robinson returned to the starting line-up whilst Alan Power returned from injury to take his place on the bench for this Blue Square Bet Premier game at high-flying Wrexham.
Mills replaced Mamadou Fofana in midfield whilst Robinson came in for Colin Larkin up front. Positional changes, meanwhile, saw Dan Gray partner Mills in the middle of the park with Peter Bore dropping to right-back. Nicky Nicolau and Adam Smith began on the left and right respectively.
Wrexham, skippered by ex-Imp Dean Keates, kicked off but when the ball was played forward, Bore played a quick ball over the top for Jamie Taylor to run on to. The striker, with only 'keeper Andy Coughlin to beat, slotted the ball inches the wrong side of the left-hand upright with only 17 seconds on the clock.
Bore and Taylor combined again on the minute mark when the former crossed for the latter to prod over and as the Imps kept the pressure up, Robinson tested Coughlin with a low, skidding effort from 25 yards.
With just five minutes on the clock, Wrexham were forced to make a change with Martin Riley hobbling off to be replaced by Declan Walker; the injury appearing to happen as Riley went to block Robinson's aforementioned shot.
Wrexham's first attempt at goal saw Brett Ormerod drag a low shot well wide whilst their second foray forward saw Danny Wright come close to connecting with a cross from the left only for the ball to fly straight out for a goal-kick.
Shortly afterwards, the hosts won the first corner of the game which City dealt with but with a number of decisions going Wrexham's way the Welsh outfit were starting to get themselves into the game with one such free-kick leading to another unproductive corner in the 18th minute.
City responded though and a couple of minutes later took a deserved lead when, after a quick break down the right saw Robinson gain possession and after his cross was half-cleared, Dan Gray drilled in a shot which fell straight to Nicky Nicolau who took a touch before rifling past Coughlin for his fourth of the season.
Shortly after the restart Coughlin got down low to claim a Taylor effort before there was a break in play when Adam Smith picked up a knock to his head following an aerial challenge in the Cit half.
A Bore throw-in led to the Imps' first corner as the clock ticked into its 25th minute and Nicolau's inswinger was punched over his own bar by Coughlin for another attempt which was cleared by the Wrexham back-line.
At the other end Paul Farman claimed an Andy Morrell shot at the second attempt but it wasn't long before the Imps were pushing forward again with Robinson putting the home defence under pressure, winning another corner which was hurriedly hacked away.
As the half-hour mark approached Peter Gilbert was left grounded by an apparent elbow from Clark. The incident was spotted by the referee's assistant but after consultation, match official Brett Huxtable felt that a ticking off for the Wrexham man was all that was needed, much to the consternation of City boss David Holdsworth on the touchline.
More drama followed in the 32nd minute as, with Tom Miller grounded in the centre circle after falling awkwardly, Taylor slid in late on Walker who duly got up and dumped the City striker to the deck, courtesy of a push to the chest.
With players from both sides converging and Miller eventually able to receive treatment, referee Huxtable calmed things down he deservedly booked Taylor but Walker somehow escaped with only a yellow card, despite the offence
With the sun emerging, temperatures on the pitch continued to rise with Wright going in late on Gilbert for another caution four minutes later. A deflected cross from John Hunt then led to a Wrexham corner which in turn led to another as the hosts pushed for a leveller. Another flag-kick followed for the hosts but City stood firm again as the half-time break approached.
A aerial challenge between Mills and Clarke then saw the City man remain grounded with Mr Huxtable again spotting nothing untoward. With the skipper helped off before returning, the Fourth Official indicated that a minimum of five minutes were to be added on.
Dan Gray was cautioned 90 seconds into added time for what referee Huxtable deemed to be the delaying of the taking of a throw-in and when the throw was taken, the City man was pushed in the back for a free-kick which eventually led to a corner.
It was Adam Smith's turn to exercise the referee's writing hand as his delay in taking this flag-kick saw him pick up a yellow card and the half eventually ended after over six additional minutes were played.
HT: Wrexham 0 Imps 1
With the main talking point during the break being the performance of the referee, both sides emerged as Mr Huxtable got things underway again.
Wrexham were the first to press following the restart but the move ended when Adrian Cieslewicz left a foot in on Bore whilst shortly afterwards a home free-kick ended with Bore hacking off his line for a corner. The hosts kept up the pressure with good defending by Miller seeing him get in front of Chris Westwood before the pressure was eased when Farman was pushed in the back following another flag-kick.
City's response to this early threat saw Robinson drill a snap-shot across the face of the goal having done well to turn his marker. It wasn't long though before the Imps were pushing forward and, 11 minutes into the second period, Jamie Taylor doubled the advantage with a top quality strike. The striker's fifth of the campaign came after Mills had found Nicolau who in turn fed Taylor who spun his man before curling home a superb 25-yard effort which gave Coughlin no chance between the Wrexham sticks.
Shortly afterwards the Imps had what looked to be a great shout for a penalty when Robinson was dragged to the floor after skipping past a number of challenges but with the appeals falling on deaf ears Nicolau was denied by Coughlin at his near post as he drilled the loose ball goalwards.
With Smith treading a fine line following his first half booking, the winger was replaced by Jake Sheridan for the remaining 25 minutes. Four minutes later City extended their lead with Robinson fire home a low effort after the teenager latched on to a weak clearance after centre-back Tom Miller went on a surging run down the left before crossing into the danger area.
City remained on the offensive with Sheridan winning a fifth corner and in a bid to get back into the game Jay Colbeck and Nick Rushton replaced Andy Morrell and Declan Walker for the home side.
Colin Larkin, meanwhile, replaced Jamie Taylor with just under 15 minutes remaining and a couple of minutes later Farman parried a Keates free-kick before blocking the follow-up effort to preserve the three-goal advantage.
That advantage was reduced, however, a minute later when a long ball down the middle was knocked down for substitute Colbeck to volley past an exposed Farman to give his side a glimmer of hope with 11 minutes on the clock.
City were on the defensive again with Mills conceding a 10th corner which ended up seeing Gray grounded and holding his nose before Ormerod saw his hooked effort crash against Miller with appeals for handball being laughed off by the officials.
A succession of throw-ins helped the Imps eat up some seconds before Alan Power made a welcome return from injury to replace Robinson. It was another subsitute, however, who added to the scoreline as within the space of 60 seconds Colin Larkin latched on to a superb cross-field pass from Nicolau and after he cut inside his marker, finished neatly past Coughlin for his first City goal from open play.
A minute later Nicolau came close to making it 5-1 when he curled a superb effort goalwards only for the ball to crash against the post but within 30 seconds a sixth goal did come, but it was the home side who bagged it with Clarke firing past Farman after a long ball forward was knocked into his path.
City had three additional minutes to see out and this they duly did with the 4-2 result a more than deserved outcome for the tremendous team effort that was on show throughout the duration of the game.
FT: Wrexham 2 Imps 4
City: Paul Farman, Peter Bore, Andrew Boyce, Tom Miller, Peter Gilbert, Gary Mills, Dan Gray, Nicky Nicolau, Adam Smith, Conner Robinson, Jamie Taylor.
subs: Alan Power (for Robinson 86), Jake Sheridan (for Smith 65), Colin Larkin (for Taylor 76), Mamadou Fofana, Jake Turner.
goals: Nicolau (20), Taylor (56), Robinson (69), Larkin (88)
bookings: Taylor (33), Gray (45+2), Smith (45+4)
Wrexham: Andy Coughlin, Stephen Wright, Martin Riley, Adrian Cieslewicz, Danny Wright, Brett Ormerod, Andy Morrell, Dean Keates, Joe Clarke, John Hunt, Chris Westwood.
subs: Declan Walker (for Riley 5), Nick Rushton (for Walker 74), Jay Colbeck (for Morrell 73), Danny Devine, Jamie Morton.
goals: Colbeck (79), Clarke (90+1)
bookings: Walker (33), Wright (37)
Referee: Brett Huxtable
Assistants: Richard Woodward & Lewis Price
Fourth Official: Craig Taylor
Attendance: 3,809 (161 City supporters)