Murray Davidson's goal after 83 minutes appeared to have the hosts on course for a place in the quarter-finals before Jamie Hamill netted an injury-time equaliser from the penalty spot.
St Johnstone dominated the majority of extra time but Zaliukas prodded home three minutes from the end of extra-time after the home defence failed to deal with Hamill's dangerous corner.
After a making a bright start to the match, the hosts created their first chance after four minutes.
Liam Craig's fizzing delivery caused unrest amongst the Hearts defence and the ball eventually broke to Cillian Sheridan who lashed an effort just wide of the target.
St Johnstone created their best chance of the first half when Sheridan forced Jamie MacDonald to make an excellent low diving stop after 26 minutes.
After being on the back foot for much of the early stages, the visitors responded just before the half-hour mark as Rudi Skacel's shot forced Alan Mannus into an excellent stop.
Hearts began the second half by forcing a flurry of corners and they almost grabbed the lead in fortuitous circumstances when Mehdi Taouil's stinging drive stuck Zaliukas, however, the ball drifted just past the post with Mannus beaten.
Chris Millar shot wide for the hosts as they tried to regain their grip on the encounter.
Millar tested MacDonald again on the hour mark when his looping cross evaded all inside the penalty area and almost dipped underneath the crossbar.
Paulo Sergio introduced David Templeton in place of David Obua after 63 minutes as the visitors tried to increase their attacking threat.
Templeton quickly made an impact as he laid on Stephen Elliott minutes after coming on, but the Irish striker failed to trouble Mannus with his low effort.
Scott Robinson blazed over when in a promising position much to the dismay of large travelling support, as both goalkeepers remained virtual spectators.
Sergio made his final change of the evening with 10 minutes remaining when Suso Santana came on for Taouil.
It was the home side who broke the deadlock with seven minutes remaining when Lee Croft broke down the right and slipped the ball inside to Davidson who prodded the ball high into the net.
Hearts almost responded instantly when Templeton jinked through three defenders but struck just inches wide of the post.
Adrian Mrowiec was next to come close as the visitors searched for an equaliser but was denied by an excellent block by David McCracken.
Hearts were handed a glorious opportunity to take the tie into extra-time when Santana was brought down inside the area by Alan Maybury.
Hamill stepped up to take the kick after furious protests from Maybury and sent Mannus the wrong way.
Sandaza almost restored the home side's advantage in the first minute of extra time but his curling effort was inches too high.
Steve Lomas increased his attacking options by bringing Canadian striker Marcus Haber on for Maybury and the change almost paid off instantly.
Craig's corner was not properly cleared and only a series of important blocks ensured Hearts remained on level terms.
St Johnstone continued to dominate proceedings and MacDonald produced a fantastic close-range save from Sandaza after a well worked corner.
Elliott flashed a shot wide as Hearts had their first attempt of extra time and Templeton's fierce effort was deflected off the line by Craig.
Hearts took the lead from the resulting corner. St Johnstone failed to deal with Hamill's centre and the ball was eventually bundled into the net by Zaliukas.
The hosts threw men forward in search of an equaliser but in a frantic conclusion they could not make a vital breakthrough.