Neither side could find a goal in normal time forcing the fixture into an additional half an hour, where the Glovers managed to take the lead after 103 minutes when a Hedges free-kick caused chaos in the Walsall box which resulted in an own goal.
After the short break Town added to their lead when Matt Dolan scored a contender for goal of the season from the halfway line after capitalising on the home keeper straying from his line with a little over five minutes remaining.
The visitors comfortably saw out the remaining few minutes to claim their place in the next round after a pulsating victory in the West Midlands.
Darren Way made just one change from the side that opened the league campaign last Saturday with a 2-0 win against Notts County at Huish Park – Bournemouth loanee Matt Butcher came in at the back for the injured Nathan Smith.
The Glovers enjoyed the better of the first half looking comfortable in possession and stifling Walsall’s attacking threat going forward.
After a bright start it was Yeovil who looked most likely to open the scoring in the opening half an hour; firstly, Otis Khan fired at home keeper Neil Etheridge after cutting in from the right before Ryan Hedges’ effort on the opposite wing was only thwarted by a fine diving save by the Philippines international.
In fact, it was the latter who came closest to scoring in the first half overall as a devastating counter-attack from Yeovil ended with Hedges side-footing Liam Shephard’s cut-back over the bar from inside the box.
Walsall were continually frustrated in the final third as the diminutive Erhun Oztumer had a shot parried for a corner by Artur Krysiak just before the 25-minute mark, before Simeon Jackson’s effort from 10 yards was emphatically blocked by Ryan Dickson after 38 minutes.
Fresh from scoring on the opening day of the season, Kevin Dawson tried an effort from 20 yards which flashed wide of the post, as the midfield trio of Dawson, Lawless and Dolan enjoyed plenty of the ball in the first period.
Etheridge was forced into another diving save before the break, this time to deny Tom Eaves who managed to glance on Hedges’ whipped free-kick from the right as the visitors ended the half in positive fashion.
Walsall, who play their football a division higher than the Glovers in League One, started the second half brightly with succession of early corners, although they were unable to test Krysiak in the Yeovil goal.
Darren Way’s side were dealt a blow just before the hour mark, however, as Liam Shephard picked up an injury after being fouled – despite trying to continue the Wales Under-21 international was replaced by Bevis Mugabi who took to the field to make his Yeovil debut.
The change didn’t interrupt the Glovers’ rhythm though as Khan once again caused mischief in the final third. Former Yeovil player Joe Edwards misjudged a long Krysiak kick allowing the winger to charge through on goal, only for Etheridge to save with his feet.
As the end-to-end action continued, Kieron Morris saw an effort fly narrowly wide of the target before Saddlers substitute Andreas Makris had a close range shot saved brilliantly by the feet of Krysiak as both sides searched for a winner in the EFL Cup.
From a corner Alex Lacey had a shot blocked on the line before Hedges’ mazy run on the edge of the Walsall box ended with an effort just over the bar with a little under 20 minutes remaining of normal time.
As the game entered the final quarter of an hour the hosts squandered their best chance of the game when substitute Amadou Bakayoko’s cross could only be headed wide by Jackson from six yards as both sides pressed for a late winner.
Jackson went close again in the last five minutes of normal time when his deflected header fell just wide of the target before Matt Dolan’s last ditch free-kick had to be tipped round the post by Etheridge to deny Way’s side a dramatic win. Instead, neither side could find a winner in 90 minutes forcing the EFL Cup match into extra-time.
In a slightly scrappier first half of extra-time both Eaves for Yeovil and Henry for Walsall went close with efforts, whilst Way introduced Tahvon Campbell for Otis Khan in a bid to find the elusive opening goal.
And the substitute played a pivotal role as the Glovers took the lead after 103 minutes. The winger was fouled wide on the left by Matt Preston and from the following Hedges free-kick, Kevin Dawson’s header back across goal was diverted into his own net by Bakayoko to put Yeovil 1-0 up.
That was the final action of the first half of extra-time but things got better after the break for Town.
With 111 minutes on the clock Glovers midfielder Matt Dolan scored an early contender for goal of the season to put his side 2-0 up.
Etheridge took a Walsall free-kick wide on the right hand side midway inside his own half only for the ball to make its way to Dolan who fired an effort from the halfway line which flew into the net before the recovering Walsall keeper could get back between the sticks.
The goal sparked a mass exodus amongst the home supporters in the stands and Yeovil comfortably saw out the remaining few minutes to see out a memorable 2-0 victory in the EFL Cup to safely see them through to the second round.
Yeovil: Krysiak; Shephard (Mugabi 54’), Butcher, Lacey, Dickson; Dawson, Lawless, Dolan; Hedges, Eaves (Sowumni 115’), Khan (Campbell 101’).
Subs not used: Maddison, Lea.
Walsall: Etheridge; Edwards, McCarthy, Preston, Henry; Morris, Chambers, Dobson (Kinsella 70’), Ginnelly (Makris 63’); Oztumer (Bakayoko 70’), Jackson.
Subs not used: MacGillivray, Butterfield, Roberts, Kouhyar.