An Aissa Mandi own-goal broke the deadlock and Naim Sliti converted a penalty as the Tunisians atoned for a 2-0 defeat by Senegal in their opening Group B game.
Substitute Sofiane Hanni scored a consolation goal for the Algerian Desert Foxes a minute into stoppage time.
Among the pre-tournament favourites, Algeria have only one point from two matches and must defeat top-ranked African team Senegal next Monday to have a chance of survival.
Senegal will become the first qualifiers for the quarter-finals if they defeat Zimbabwe later Thursday in the second part of a double-header.
"It was a very important match," said Sliti. "We knew that after the match against Senegal that we were very frustrated. We had the chances to win.
"Today we made amends and showed the true face of Tunisian football. Many say that we play the most beautiful football and today we were rewarded."
Belgium-born Algeria coach Georges Leekens said: "We started very well, but we know that in a match of this level we cannot give away gifts.
"If we make them two presents in the second half, we cannot win. The way we conceded the second goal when we were hit on the counter attack, we cannot have imagined that before the game."
Although the northern neighbours have been regular competitors at the biennial African football showcase, this was only their second Cup of Nations meeting.
The Carthage Eagles - as Tunisia are known - won 1-0 at the group stage in 2013 thanks to a stoppage-time goal from Youssef Msakni, a starter in Franceville.
Tunisia's Aymen Mathlouthi was much the busier goalkeeper during the opening half in the southeastern Gabonese city.
The vastly experienced shot-stopper used his hands and legs to foil Yacine Brahimi, Islam Slimani, Adlane Guedioura and 2016 African Footballer of the Year Riyad Mahrez.
A free-kick from midfielder Brahimi was millimetres off target before Mathlouthi thwarted striker Slimani by stretching his left leg to push away a header.
Good positioning by the goalkeeper foiled Guedioura when the midfielder unleashed a stinging shot from outside the box.
Mathlouthi then dived swiftly to his right and foiled Mahrez, scorer of both goals in a 2-2 opening-round draw with Zimbabwe four days ago
Tunisia came closest to scoring in the first half when the quick reactions of Algerian goalkeeper Malek Asselah prevented the ball crossing the line.
Having weathered the first-half Algerian storm, Tunisia took the lead five minutes into the second half.
A throw-in and a flick set Msakni free and his intended cross was deflected by Mandi into his own net.
The goal rattled the Desert Foxes and they fell further behind on 66 minutes.
A Faouzi Ghoulam back-header aimed at his goalkeeper was far too weak and he then fouled Wahbi Khazri to concede a penalty.
Sliti calmly scored from the spot, placing the ball in the right corner as Asselah dived the wrong way.