Two wins in the trot, blimey that's been a while, and it was debutant keeper Rhys Evans who was the hero of the night making two penalty saves while son of Luggy Blair Sturrock stepped up to hit the winning spot kick. (In all honesty Rhys had litle to do before the penalty drama at the end, but deserves his MOM just for that.)
Blues boss Paul Sturrock made two changes to his starting line-up from Bradford with the hero to be Evans making his first start for the club in place of Glenn Morris, while midfielder Adam Bouzid replaces the suspended Sean Clohessy.
This meant Josh Simpson reverted to right back as predicted, with Chris Barker continuing as a central defender after completing his permanent move from Plymouth Argyle earlier in the day.
Following a goalless, and rather forgettable, 90 minutes at Roots Hall on Tuesday evening, the match went to spot-kicks and the scores were level at 3-3 after both teams had a penalty saved and missed another.
The first of the sudden death penalties, no extra-time in the JPT which must have been good news to the Shrimpers who had spent 122 minutes on the field of play at Wolves last week before losing in the last seconds, saw Jack Payne's effort saved by Evans, before Sturrock fired into the right hand side of Gills keeper Lance Cronin's goal.
And so Southend United were in the second round of the competition for third and fourth tier clubs for the first time since 2005, after Tilly had guided them to two successive Cardiff finals earlier on in the decade when it was known as the LDV Vans Trophy.
Cronin had earlier done well to turn over an early Barry Corr header from a Ryan Hall cross, before denying the other Shrimpers player making his debut, the French Tunisian midfielder Adam Bouzid, with his feet this time around.
At the interval Louie Soares and Sofiene Zabboub came on for Bouzid and Hall, with Matt Paterson replacing Corr in the 64th minute.
The Gills shot stopper was certainly the busiest between the posts, saving two Sturrock efforts in the second half, the latter, when Blair was clean through, with his legs again, while Anthony Grant, in his 100th game for the Blues, pulled a twenty yarder wide of the right-hand post.
Gillingham had the odd chance, Cody McDonald heading wide early on, Tony Sinclair seeing a shot blocked by Bilel Mohsni, and John Nutter had a couple of efforts, one a free-kick that was deflected over the bar.
So to penalties, and Stefan Payne was the first to have his kept out by Evans, but it was all square when after Soares had scored his, skipper Craig Easton had his saved by Cronin.
Four spot-kicks were all converted in a row, including one by Kevin Maher, making it 3-3, Barker and Paterson for the Essex boys, before Danny Spiller sent his into the cheering South Bank..........Granty then to take the plaudits on his big night.
Sadly not, Cronin diving down low to keep that out.
Up stepped Jack Payne for the Gills, and back he went with his head in his hands, Evans saved again, with his right foot this time!
So it was Blair Sturrock, who many have accused of only being in the side because of Daddy, certain correspondants on this site included, and who knows there may be some truth in it, but nobody cared when he smashed the ball home to send the Roots Hall faithful home in a rather happy mood.
The defeat leaves the Kent based club, and ex-captain Maher, could you tell him apart from captain Craig, still looking for their first victory of the season, while on the other hand Southend will face 100% Torquay at Roots Hall on Saturday with more confidence than they could have imagined a week ago.
Southend player markings: Evans - 8, Gilbert - 6, Barker - 7, Moshni - 7, Simpson -6, Grant - 6, Easton - 6, Bouzid - 5 (Soares - 6), Hall - 6 (Zabboub 6), Corr - 7 (Paterson - 6), Sturrock - 6.
Referee: Gavin Ward (Surrey) - 5.
Southend United: Evans, Simpson, Mohsni, Gilbert, Gilbert, Bouzid (Soares h-t), Easton, Grant, Hall (Zaaboub h-t), Sturrock, Corr (Paterson 64)
Subs not used: Morris, Coughlan
Gillingham: Cronin, Fuller, Gowling, Sinclair, Nutter, J Payne, Maher, Rooney (Barcham 60) , Spiller, McCammon, McDonald (S Payne 68)
Subs not used: Julian, White, Essam.
Attendance: 3, 073 (Gills 426)
Yellow Card: Gillingham - Sinclair 84mins (foul).