The two teams went into tonight's second leg all square following a goalless draw in Malta a week ago, but it was the visitors who progressed to set up a meeting with Krasnodar in the next round.
Hearts almost found themselves behind inside two minutes when Jack Hamilton was forced into a point-blank save early on, but that was a rare sight of goal for either side in the opening exchanges.
The hosts were gifted a glorious chance to take the lead in the tie with 10 minutes left of the first half when Sam Nicholson was brought down by Christian Bubalovic inside the penalty area, but Birkirkara keeper Miroslav Kopri kept out Prince Buaben's spot kick.
Faycal Rherras was the next to come close for Robbie Neilson's side when he surged forward down the left flank before cutting inside and going for goal, but his effort curled narrowly past the far post.
Despite the setback of a missed penalty, the hosts continued to look the most likely to break the deadlock in the first half, and it took a goalline clearance to deny Walker in the closing stages after Kopri had been caught out next to his own corner flag.
Arnaud Sutchuin Djoum dragged the hosts' first clear sight of goal in the second half wide of the target, and Hearts were eventually made to rue their missed opportunities.
Birkirkara took a shock lead 10 minutes after the restart when the ball fell to Bubalovic inside the box following a scramble, and the defender atoned for his earlier foul in the penalty area by firing his volley past Hamilton.
Hearts were inches away from coming up with an equaliser within two minutes of falling behind, but for the second time they were denied by the crossbar when Nicholson cut inside and curled an effort against the woodwork.
With two goals needed to advance, Hearts piled forward in search of the first and it took a decent stop from Kopric to deny Juanma shortly before the hour mark, while Djoum blazed the rebound over the bar.
The hosts' hopes of qualifying were dealt a hammer blow with less than 25 minutes remaining, though, as Birkirkara doubled their advantage, hitting Hearts on the break before Edward Herrera applied the finishing touch.
This time Hearts were able to respond quickly, though, and they cut the deficit back to one just six minutes later when Conor Sammon steered a header from Djoum's cross beyond the keeper.
The Jambos still needed two goals to go through, and they never looked like getting them in the closing stages, with a dragged Djoum effort the closest they came to at least levelling things on the night.
Neilson's side were not even able to do that, though, as they crashed out of Europe with a whimper, while Birkirkara progress to take on Krasnodar.