After the break, Bounedjah hit the bar from the spot after earning Algeria a penalty, and they were made to pay just after the hour-mark when the Ivory Coast equalised through Aston Villa forward Jonathan Kodjia, who rode a tackle before firing a superb effort into the far corner.
Algeria beat Ivory Coast on penalties
The match ultimately went the distance, and after five perfect penalties, Wilfried Bony saw his penalty saved, and though Youcef Belaili could only hit the post with Algeria’s fifth penalty, Serey Die did likewise to send the Ivory Coast packing.
It was the Ivorians who started the brighter of the two teams, with Max Gradel rattling the post from distance and Kodjia failing to apply the finish from close range after superb work from Wilfried Zaha on the right.
Algeria had already shown a threat, with Riyad Mahrez dragging a decent effort wide before they took the lead. Bagayoko rashly challenged Bounedjah and the loose ball fell to Bensebaini, who squared it to Feghouli to finish wonderfully.
The first five minutes of the second half saw plenty of drama. Firstly, Algeria missed a golden opportunity to double their lead, with Bounedjah missing a penalty he took after being cleaned out by Sylvain Gbohouo.
Seconds later, Kodjia's attempted pass across the Algerian box took a nick off Aissa Mandi and hit the bar. Eventually, Bounedjah's penalty miss proved costly, with Kodjia gathering a ball from Zaha brilliantly, skipping past his maker and driving the ball into the bottom corner.
That was enough to force extra time, which failed to separate the two teams. In the shoot-out, Raiss M'Bolhi saved Wilfried Bony's effort and although Youcef Belaili hit the post, a subsequent miss from Serey Die sent the Algerians through.
Can Algeria cut out the histrionics?
A running theme of this match was Algeria losing their cool. Bensebaini made farcical attempts to get Zaha sent off in the first half, including an incredible moment where he grabbed the Crystal Palace forward's arm and hit himself in the face, Ounass proved himself to be very happy to go down under no contact to win penalties and Bounedjah completely was visibly distraught after he missed his penalty. If they are to win the title, they will need the mentality of champions.
MAN OF THE MATCH -
Raiss M'Bolhi (Algeria) - He may have had some nervy moments but you cannot deny that the Algerian goalkeeper was key to his side's progression today as he made some key saves in normal play before denying Bony from the spot in the shoot-out.
6' So close! - Gradel shifts the ball on to his right foot and takes aim. It looks like his effort is going to give his side an early lead but M'Bolhi just gets finger tips to it and tips it on to the post. The rebound came at Kodjia too quickly for the Aston Villa man to react.
20' GOAL! - Algeria take the lead. Bensebaini takes advantage of a loose ball after Bagayoko's botched challenge on Bounedjah, advances into the box and squares it to Feghouli, who finishes with aplomb!
48' MISS! - Bounedjah takes the penalty himself and his shot goes over off the top of the bar! He looks distraught and Ivory Coast will have the wind in their sails now.
62' GOAL!! - Ivory Coast are back on level terms! Kodjia takes down a high ball, rides a challenge from Benlamri and blasts a left-footed shot past M'Bolhi and into the bottom corner. Game on!
Penalties: Serey Die for Ivory Coast... OFF THE POST! Algeria go through!
This is only the second time Algeria have reached the semi-finals at the Africa Cup of Nations since they won the title on home soil in 1990.