After a hesitant first 10 minutes, the game soon picked up speed, with Mali midfielder Lassana Samake playing a dangerous cross into the Uganda box, only for Bernard Muwanga to clear at the near-post.
Joseph Ochaya then headed the Ugandans in front from a well-taken a set-piece, only for man-of-the-match Sedou Keita to make even 12 minutes later, with a powerful left-footed shot from just inside the penalty area.
The match soon developped into an attacking contest, as well as a physical one, with action at both ends of the pitch.
In the 32nd minute, Keziron Kizito's thunderous shot forced a dramatic save from Mali goalkeeper Djigui Diarra.
Five miutes later, Mali's Abdoulaye Traoré raced down the left-hand side and whipped in a dangerous cross, which Uganda keeper Isma Watenga collected with ease.
With four minutes left before half-time, the Cranes were then awarded a decisive penalty, when Erisa Sekisambu was brought down inside the box.
Uganda captain Miya stepped up to convert the spot-kick, putting his team in front, before picking up an injury and being replaced by Muzamiru Mutyaba.
More drama followed in the second half, when Uganda goalkeeper Isma Watenga sustained a muscle injury when taking a goal kick, and had to be replaced by Mathias Kigonya.
Having lost both their captain and their goalkeeper, the Cranes struggled to dominate the game, and looked hesitant.
Mali took charge of the match, harrassing Uganda's defense with several waves of attack.
On the hour mark, the Eagles' determination paid off, when Hamidou Sinayoko tapped in Mamadou Coulibaly's cross, making it 2-2.
Uganda, fought back, eager to steal the winner, and forced a formidable save from Malian goalkeeper Djigui Diarra.
With eight minutes remaining, Mali then pushed forward, forcing Uganda's substitute goalkeeper Kigonya to a desperate save in a one-on-one with Sinayoko.
Uganda and Mali enter the 2016 African Championship joint second in group D, two points behind leaders Zambia, who beat Zimbabwe 1-0 in the earlier group opener.
Uganda can take pride in holding off a side largely considered the favorite in the group.
But the loss of both their charismatic captain and their goalkeeper at the start of the tournament will be a major blow for Milutin 'Micho' Sredojevic's men.