The 2008 winners eventually progressed at the Mestalla but not before they were given a tough examination from their third-tier opponentsValencia began life without fired coach Miroslav Djukic by scraping into the Copa del Rey last 16 with a 1-0 second-leg victory over Gimnastic.
Having been held to a goalless draw on the road in the first leg, Valencia will have been feeling more than confident about sealing their progression on home turf against third-tier opposition.
However, that proved to be easier said than done, as the hosts - under the temporary charge of Nico Estevez - struggled to break down their visitors at a sparsely populated Mestalla.
Paco Alcacer handed the Liga side the advantage in the 37th minute, before a foul on Pablo Piatti in the area late on offered substitute Helder Postiga the opportunity to double Valencia's lead from the spot.
But it proved to be an opportunity wasted as Tomeu Nadal got down well to keep out the strike and restrict Valencia, who will now take on Atletico Madrid, to a one-goal victory.
At San Mames, Athletic Bilbao stormed to a 4-0 victory over 10-man Celta Vigo to sail into a last-16 meeting with Real Betis, prevailing 4-1 on aggregate.
Iker Muniain put the hosts in front after 21 minutes, smashing home from the edge of the penalty area after a delightful flick by Aritz Aduriz.
Markel Susaeta doubled that advantage a minute short of the break, with Hugo Mallo dismissed early in the second half, before a second Muniain strike and one for Aduriz put the result beyond all doubt.
Elsewhere, Espanyol imposed their superiority as they overcame Segunda Division Real Jaen 2-0 to seal a 4-2 aggregate victory.
Simao opened the scoring for the hosts in the 12th minute, before Sidnei's strike five minutes from time secured a showdown with second-tier Alcoron.
Real Valladolid's Javi Guerra played the part of both hero and villain as his side crashed out 3-1 to Rayo Vallecano.
Following a goalless first leg, Guerra drew first blood by sending the visitors into a 28th-minute lead at Estadio del Rayo Vallecano, before Adrian drew the hosts level four minutes later.
Guerra was shown a straight red card three minutes into the second half and Valladolid failed to recover from that setback.
Adrian put the hosts ahead in the 87th minute with his second of the match, before Alberto Bueno made absolutely certain of the win in stoppage time.
Rayo will meet Levante in the next round.