Worthing came back from two goals behind to wrap up a 3-2 victory after extra-time to set up a second round qualifying date with National League South St Albans City.
Efforts in either half from Craig Stone and ex-Worthing striker Ben Pope had put the U's in control.
However, Lloyd Dawes and substitute Ollie Pearce netted in the final 13 minutes to force extra-time.
Just as it looked as though the replay would be decided on penalties, Armstrong headed home to secure Worthing's progress as they secured £4,500 in prize money.
Worthing made five changes from the team that drew 3-3 in the original tie on Saturday.
Former Portsmouth triallist Olly Long was handed his debut while Lloyd Dawes, Mason Doughty, Shola Ayoola and Joe Tennent all came in for starts. They replaced Marvin Armstrong, Ricky Aguiar, Ross Edwards, Ollie Pearce and Jasper Pattenden.
Worthing were slow out of the traps and sloppy in possession early on. Hastings sensed nervousness across the hosts' backline and were pressing high up, nearly going ahead after 12 minutes.
Danny Barker was caught on the ball on the edge of the box by Lanre Azeez. He then tried to pick out Jack Dixon but Roco Rees pounced to collect the loose ball.
But Hastings did get the goal their early pressure deserved on 16 minutes. The hosts failed to clear a corner and Craig Stone was on hand to thunder home from 20 yards.
Worthing then had a combination of Rees and defender Joe Tennent to thank for not falling further behind two minutes later.
Daniel Ajakaiye was sent racing away, only to see his shot kept out by the feet of Rees before Tennent headed away off the line.
The hosts were still looking sloppy in possession but did manage to test Louis Rogers in the Hastings goal a couple times before the break.
Forwards Shola Ayoola and Mason Doughty both saw tame efforts easily held as the U's went in leading 1-0 at the break.
Worthing made the worst possible start to the second half, falling two goals behind on 47 minutes.
Goalkeeper Rogers' long pass sent former Worthing striker Ben Pope racing away and he slotted past Rees.
But defender Jalen Jones so nearly handed the hosts a lifeline on 53 minutes, although his poke towards goal was kept out by Rogers.
Hastings were still carrying a real threat on the counter attack and livewire Ajakaiye came close to putting the tie beyond Worthing a minute later.
The pacy winger once again raced away before cutting inside but his strike was parried away by Rees.
Substitute Marvin Amrstrong then came close to pulling one back for Worthing after 68 minutes as they looked for a way back in. Defender Jones picked out the midfielder in the area but Rogers kept his effort out.
The hosts must have been thinking it wasn't to be their night when Rogers pulled off a fine stop to keep out Dawes' bullet header 14 minutes from time.
Yet from the resulting corner, the forward's header from substitute Ricky Aguiar's corner forced through the fingers of the Hastings goalkeeper to hand Worthing hope.
Manager Hinshelwood's substitutions then played their part as the hosts levelled six minutes from time.
Aguiar, introduced in place of Doughty, saw his shot parried by Rogers and substitute Pearce was quickest to the loose ball to poke home.
Midfielder Aguiar was again involved, going down in the area under a challenge in stoppage-time but the protests were waved away and extra-time was forced.
Substitute Kenny Pogue just failed to get on the end of Ryan Worrall's cross as the visitors had the first half chance in extra-time.
Aguiar then tested Rogers with a fierce drive before Hastings managed to clear the danger after a Jones header from a corner as neither side could find a goal in the first half of extra-time.
Just as it looked as though the replay would be decided on penalties, substitute Armstrong headed home Jesse Starkey's free-kick to secure Worthing's progress on 118 minutes.
WORTHING: Rees; Colbran, Tennent, Jones; Dawes, Barker, Starkey, Meekums; Doughty, Long; Ayoola. Subs: Pattenden (Dawes, 110), Pearce (Ayoola, 74), Armstrong (Long, 57), Mendoza, Edwards, Aguiar (Doughty, 57), Stevens.