The Pharaohs had the upper hand and created most of the chances in the half.
The first real chance of the game came in the 17th minute when Omar Marmoush rattled the Ivorian bar with a fierce effort off a sloppy play from the Cote d'Ivoire defense.
Five minutes later, Mohamed would be denied by the Ivory Coast goalkeeper who produced a one-handed save to deny the Liverpool man.
At the half-hour mark, with Egypt dominant and threatening, Ivory Coast lost their mercurial midfielder, Franck Kessie to injury with Serey Die taking his place.
Moments later, Bandra Sangare, the Ivorian goalkeeper was forced into making a double save in the space of one minute to deny Mostafa Mohamed and then, Salah.
Ivory Coast finally had their first chance of the game in the 38th minute, Ibrahim Sangare's spectacular effort forced goalkeeper Mohamed El Shenawi into his first real save of the game.
Sebastien Haller, who had a quiet half, almost found the breakthrough in the first half added time after he found space for a snap-shot that Egypt's goalkeeper gathered twice.
An exciting opening half saw Ivory Coast and Egypt level at the break as there was nothing to separate them.
In the second half, it was Egypt who continued from where they stopped and had the chance to break the deadlock six minutes in.
The Pharaohs had just two great chances to open the scoring ten minutes into the second 45.
Mo Salah does very well from the right to set up youngster Mohamed but with just the goalkeeper to beat, he 'rugbys' his shot before El Neny's deflected shot almost found its way in but goalkeeper Sangare saved superbly to keep the score goalless.
Cote d'Ivoire survived the early scare to create good chances of their own, with goalkeeper El Shenawy denying Haller twice in two minutes.
Egypt's substitute Trezequet had a good chance to put his side ahead moments after coming on but failed to direct his effort at goal from close range in the 73rd minute.
Wilfred Zaha came on for Ivory Coast and forced a superb save from El Shenawy before the Al Ahli shot-stopper was forced off due to an injury late on.
There was still nothing to separate the two teams after the regular time and the match went into extra time to decide the winner.
The extra time produced little excitement with the best chance of the first half coming Ivory Coast's way.
PSV star Sangare's audacious attempt from just outside the box was superbly saved by Egypt's substitute goalkeeper to keep the Pharaohs still in the game in the 104th minute.
Egypt's only real chance came at the dead when Salah's cutback found Trezequet whose tame effort was easily saved by Bandra.
Penalty shootout decided the tie, in the end, Eric Bailly was the only player to miss as Egypt defeated Cote d'Ivoire 5-4 to go through to the last eight.
The Pharaohs will go head-to-head with another familiar foe in the Atlas Lions of Morocco, while Ivory Coast heads home.