Goalkeeper Aaron McCarey saved from Craig Westcarr and Andy Taylor as Wolves won the shoot-out 4-2 in the first meeting between the two neighbours for 10 years.
Wolves had twice taken the lead through Liam McAlinden and Bakary Sako only for Walsall to battle back through Ashley Hemmings and substitute Troy Hewitt.
Wanderers - competing in the Football League Trophy for the first time since 1989 - had looked set to cruise into the second round when McAlinden marked his full debut with his first goal for the club after just five minutes, steering the ball home from six yards after a cross from right-back Matt Doherty.
McAlinden then squandered two excellent chances to double Wolves' advantage before Hemmings, who was released by Wolves in the summer of 2012, made him pay when he was left unmarked to head home a cross from Westcarr in the 53rd minute.
Sako then put Wolves back in control 10 minutes later after Adam Chambers pulled down Danny Batth in the penalty area. The Frenchman's spot-kick was saved by Richard O'Donnell but Sako reacted fastest to turn home the rebound.
Yet Chambers then made amends for giving away the penalty with a neat knock-down to tee up Hewitt, who made no mistake from close range to take the game to penalties.