Substitute Laryea Kingston was shown a straight red card seven minutes after the break for a high challenge on Fraser Fyvie but this did not prevent the visitors breaking the deadlock after 64 minutes courtesy of Eggert Jonsson's stunning overhead kick.
Despite playing for the majority of the second period with a numerical disadvantage the visitors held on for their third-successive victory.
Goalkeeper Jamie Langfield returned to the Aberdeen starting XI after dropping to the bench for last week's 3-1 defeat at Falkirk.
The Dons made three changes in all with Derek Young and Paul Marshall both handed starts with Jim Paterson missing through injury and Michael Paton and Stuart Nelson returning to the bench.
There was also a change in goal for the visitors with Janos Balogh replacing Marian Kello who was out after fracturing his wrist.
Hearts' only other change saw skipper Michael Stewart return in place of the injured Suso Santana.
The Dons enjoyed two resounding wins over the Tynecastle side last month and had the ball in the back of the Hearts net within four minutes of kick-off when Darren Mackie chipped Balogh but the goal was chalked off for offside.
Mackie was then gifted a chance to test the Hearts rearguard following Dawid Kucharski's slack clearance but the striker's pass to Steven MacLean was easily cut out by Lee Wallace.
The Jambos created their first opportunity after 14 minutes when Wallace sent a dangerous ball into the Aberdeen penalty area that was partially cleared into the path of Jonsson who blasted woefully off target.
Dons skipper Mark Kerr picked up the first booking after 16 minutes for a challenge on Calum Elliot, which looked a harsh decision.
Jonsson joined him in the referee's notebook three minutes later for a professional foul on MacLean.
Both sides were struggling on the poor Pittodrie surface, although the ball did break kindly for Richard Foster on the edge of the box after Mackie had dispossessed Elliot, but the full back's low drive found the side-netting.
Gary McDonald was shown a yellow for a string of fouls after 38 minutes before Marshall almost released MacLean, but Kucharski managed to intervene.
The Polish defender limped off with an injury just before the break and was replaced by Kingston.
The visitors had a disastrous start to the second half when the Ghana international was shown a straight red card for a high challenge on youngster Fyvie.
The 10 men of Hearts were forced to make a change after 54 minutes when Paul Mulrooney came on for Marius Zaliukas who looked to have picked up a hamstring injury.
Hearts boss Jim Jefferies then made his final substitution by bringing on Jamie Mole for the ineffective Arvydas Novikovas, while Aberdeen introduced Sone Aluko for Marshall with 30 minutes remaining.
Jonsson then gave Hearts the lead in spectacular fashion after 64 minutes. Elliot's shot was blocked by Mulgrew on the edge of the area and the ball looped into the air towards the Icelandic defender who, with his back to goal, executed a fantastic overhead kick that gave Langfield no chance.
Michael Paton, who had came on for Fyvie after 73 minutes, fired wide from distance with 10 minutes to go with perspiration replacing inspiration as the Dons pressed for an equaliser.
Hearts were forced to play with nine men temporarily when Wallace required treatment for a blood injury but Aberdeen were unable to capitalise on this additional advantage.
Aberdeen did muster a late rally but they could find no way past a resolute Hearts defence and are now eight points behind the Tynecastle side.