Gills substitute Gareth McCleary shattered County hearts as his late winner snatched deserved reward away from Christian Fuch's men in a crazy game at the MEMS Priestfield Stadium.
The diminutive striker struck nine into 15 minutes added time to nullify goals from the Port's Michael Spellman and sub Cameron Antwi in either half - this, after Conor Masterson had initially levelled for Gillingham in the opening exchanges.
Much-improved Newport seemed on target for a fourth league victory on the road after ex-Fulham starlet Antwi had stroked County ahead on 83 minutes, but Armani Little's late spot kick and than dreadlocked McCleary, off the bench after the hour, piled on the misery for the Exiles.
Even then, though, Port fought on - substitute James Crole cursing his luck after Gills keeper Glenn Morris brilliantly thwarted him from point-blank range - this before a multi-player ruck deep in the box saw County skipper Matt Baker and Gillingham's Andy Smith cautioned by referee Carl Brooke as tempers boiled over.
Port had a new look coming into this clash on the Medway. Four of the five signings made so far in the January window figured in the equation.
There was a second County debut for borrowed Swindon Town central destroyer Ryan Devaney, Harris Biggins, snapped up on loan from Shrewsbury having a bow in central midfield, alongside returning Wales international Matt Smith. Silky right back Liam Shephard started at kick off for the first time since mid-August, Nathan Opoku, who had recently extended his loan from Championship Leicester City, leading the attack.
Prolific marksman Crole, signed from JD Cymru Premier outfit Penybont and flying winger Tanatswa Nyakuhwa, on loan from League One leaders Cardiff City, were on a strong-looking Newport bench.
The Gills showed a quartet of changes from the team that went down 2-0 at Swindon's County Ground on New Year's Day. Veteran Morris, 42, came in for 640th pro game, Masterson slotted into right-back, ex-Hull man Robbie McKenzie central midfield with former Blackburn raider Bradley Dack adding bite with Josh Andrews up front.
The Stereophonics' A Thousand Trees and the Ed Sheeran hit Azizam boomed across the arena beforehand. Gillingham, without a home league win in over four months, were dancing to the County rhythm on three minutes.
Lee Jenkins' diagonal ball released a galloping Anthony Glennon on the right, the left-back's squared for advancing Biggins to expend stopper Morris with a fierce low drive.
It was a rip-roaring opening by the Exiles, who powered ahead 60 seconds later. The Gills failed to clear a set play. Jenkins' blast was initially blocked, Delaney's header was saved by Morris only for a lurking Spellman to return a looing effort into an empty net.
It was the Geordie's second goal of the season and County almost profited again - Morris pouching Jenkins' header and then snatching a menacing Smith cross with all-action Biggins ready to pounce.
The Port were needing to show resilience as Shepherd acted swiftly to snuff out Aaron Rowe at the far post and Welsh cap Jonny Williams saw his special deflect off skipper Baker over the bar.
The Gills continued to ask questions and were level on 30 minutes. Max Clark manufactured a curling delivery from the left, Masterson ghosting in to power his header past the flying Jordan Wright into the far corner.
Gillingham's blue shirts continued to flood forward as the interval loomed, but a swift Port counter so nearly punctured the hosts on 44 minutes. Bobby Kamwa. tortured Sam Gale with a step-over before skewing his right-footer wide.
Gills pressure was building, Andrews sending a header over the top after Clark had cut inside on the left - Rowe then extended Wright with a wicked effort, which the County stopper excelled in parrying away.
Yet Wright must have been grateful as the hour approached - ex-Birmingham attacker Andrews guilty of two glaring misses, the first one pouched by the Port custodian, a second somehow hooked over a unguarded goal by the striker.
County appeared to administer punishment on the wasteful Gills as they pulled in front in the 84th minute. Devaney robbed the beleaguered Andrews and released sub Nyakuhwa, the Cardiff winger's sublime ball cushioned by Antwi, before he swivelled and then fired low Morris.
But Newport joy turned to acute disbelief within the added time which had occurred on 65 minutes when a linesman needed to be replaced by the Fourth Official, an additional qualified person then required from the crowd.
On 91 minutes Nyakuhwa accidently upended McCleary in the area - Little smashing in the resulting penalty. Worse was to come later as tiny McCleary rose highest amongst a posse of players to nod in via the underneath of the bar.
Even then, Crole so nearly became a hero off the bench, Morris' agility dismaying the big Welshman.
Gillingham [4-2-3-1]
Glenn Morris
Conor Masterson
Sam Gale
Andy Smith
Max Clarke
Armani Little [C]
Robbie McKenzie
Jonny Williams
Aaron Rowe
Bradley Dack
Josh Andrews
Subs
Jake Turner [GK]
Remeao Hutton for Rowe 86 mins
Ethan Coleman for Dack 102 mins
Gareth McCleary for Williams 70 mins
Seb Palmer-Houlden
Sam Vokes for Andrews 87 mins
Elliott Nevitt
Newport County [5-4-1]]
Jordon Wright
Liam Shephard
Lee Jenkins
Matt Baker [C]
Ryan Devaney
Anthony Glennon
Mark Smith
Harrison Biggins
Michael Spellman
Bobby Kamwa
Nathan Opoku
Subs
Nik Tzanev [GK]
Tanatswa Nyakuhwa for Spellman 55 mins
James Crole for Opoku 89 mins
Ciaran Brennan for Smith 76 mins
Tom Davies
Cameron Antwi for Jenkins 76 mins
Joe Thomas for Shephard 88 mins
Referee: Carl Brook
Assistants: Danny Guest & Bradley Hall
Fourth Official: Anthony Moore
Attendance 5,548 [166]