Costa Rica had its own chances, though they were less clear cut.
A series crosses peppered Jesper Cillessen's goal but there was little to concern the men in orange until a flick from Celso Borges bounced invitingly across goal with no Costa Rican striker to tuck home.
The Dutch responded with a free kick from Sneijder that was spectacularly clawed away by Navas shortly after.
After the break, both managers looked to break the stalemate by shuffling their pack.
Marcos Urena replaced Joel Campbell up front for Los Ticos while the Dutch also made a striking change, taking off Depay for Jeremain Lens.
Then, just as it seemed the game would never break from a crawling pace, it burst into life.
Arjen Robben, who Costa Rica looked to double up on all night, burst forward and, despite accentuating what was minimal contact from Giancarlo Gonzalez, won a free kick on the edge of the box.
Sneijder stepped up and rattled the post with a vicious swerving shot before the ball was eventually cleared.
All of a sudden, the Dutch were energized and Los Ticos were rocking.
Another free kick caused chaos in the Costa Rica box and the ball dropped to Van Persie, who fired in a shot that Navas again did well to block.
As the clock struck 90 minutes the Dutch had their best chance of all as Daley Blind's low cross evaded everyone until it landed at the feet of captain Van Persie at the back post.
The Manchester United striker struck the ball goalwards with Navas stranded but his shot was met by the retreating, Yeltsin Tejeda who somehow used his body to deflect the ball onto the bar and away.
After what was for so long a sterile contest, the brief break before extra time barely seemed enough for the now clearly tiring players to catch their breath.
The Dutch again started on the front foot as Navas made another fine save from a Ron Vlaar header.
From the resultant corner, the keeper was almost caught out as he flapped at Sneijder's cross.
Klaas Jan Huntelaar was introduced at the break for defender Bruno Martins Indi as Van Gaal attempted to avoid the dreaded penalty shootout.
The striker, whose injury-time penalty won the day against Mexico,was soon booked for crashing into Navas when challenging for a high ball.
Costa Rica threatened next as substitute Urena broke free at the edge of the box, working a yard of space before firing a low shot that Cillessen dived to push away.
Even closer was to follow at the other end.
As the clock ticked down, Sneijder peeled away at the far edge of the box before setting himself and unleashing another brilliant curling strike.
For once Navas was helpless. But again the woodwork came to his rescue as the midfielder's shot bounced away of the crossbar.
Penalties it would be -- but not before Van Gaal took the unorthodox decision to replace Cillesen with Krul for the shootout.
"There is no question about who will start next game, it will be Cillessen," Van Gaal said. "But we felt Krul was the better choice here.
"We told Krul that he would be a possibility for the penalties, but we didn't tell Cillessen, as we didn't want to ruin his preparation."
It was a bold call that would prove decisive.