Hamza Rafia gave Tunisia an early lead in the 6th minute, but Madagascar capitalized on a costly error by goalkeeper Amanallah Memmiche to equalize 14 minutes later.
However, Sayfallah Ltaief put Tunisia back in front before halftime, only for Ibrahim Amada to level the score with a well-struck left-footed shot just before the break.
In dramatic fashion, Ali Al-Abdi's added-time goal sealed the win for Tunisia, who top the group with 10 points, four ahead of second-placed Comoros with just one game remaining.
Elsewhere in Group B, Lesotho's 1-0 victory over the Central African Republic moved them to third, securing qualification for Gabon.
With 7 points, Gabon sit second and will advance regardless of their upcoming match against group leaders Morocco, who have 12 points.
Should Gabon and Lesotho both finish with 7 points, Gabon will advance due to their superior head-to-head record, having won one match and drawn the other.
Meanwhile, in Group K, South Sudan's 3-2 win over Congo handed qualification to both Uganda and South Africa.
Uganda top the group with 10 points, two ahead of South Africa.
With the remaining games in Group K not affecting qualification, both Uganda and South Africa are through to the tournament.
Egypt, Cameroon, Angola, DR Congo, Burkina Faso, Senegal and Algeria have already qualified for the prestigious continental tournament.
The top two teams from each of the 12 AFCON qualifying groups will advance to the continental competition.
(For more sports news and updates, follow Ahram Online Sports on Twitter at @AO_Sports and on Facebook at AhramOnlineSports.)
Short link: