Michael Stewart scored the equaliser for Hearts at Pittodrie

Barry Nicholson fired the Dons ahead after Jamie Smith powered forward, robbed Eggert Jonsson then set up his fellow midfielder after 19 minutes.

But Kestutis Ivaskevicius set Stewart up on the stroke of half-time and the midfielder curled it in from 18 yards.

Neither goalkeeper was seriously tested in a second period of few chances.

Interview: Aberdeen manager Jimmy Calderwood

Interview: Hearts coach Stephen Frail

Hearts had made five changes from the side that lost to Hibernian on Monday.

Recent signing Ruben Palazuelos was given his debut in midfield alongside Icelandic teenager Jonsson, who was making his first start.

MY SPORT: DEBATE Give your reaction to the game at Pittodrie

New captain Christophe Berra returned from suspension, while Andrius Velicka and Ivaskevicius also returned to the starting line-up.

Aberdeen made three changes after their opening-day defeat by Dundee United.

Zander Diamond, Lee Mair and Stevie Lovell came in for Andrew Considine, Lee Miller and Richard Foster.

And the Dons were immediately on the attack, with Nicholson sending a volley straight at Steve Banks from 20 yards after pouncing on a poor clearance.

Barry Nicholson gave Aberdeen an early lead against Hearts

Hearts quickly took a grip of midfield but paid for a bit of slack defending to go one behind after 18 minutes.

Barry Smith powered past a couple of defenders then pounced on Jonsson's hesitation to clear and set up Nicholson, who slotted the ball home from 10 yards at the second attempt.

Aberdeen took heart - and control - with Hearts relying on aimless high balls through the middle.

But the Dons failed to create any clearcut chances and the dull affair did not come to life again until the stroke of half-time, when Hearts equalised against the run of play.

Velicka found Stewart lurking unmarked 18 yards out and the midfielder who left Hibs in the summer curled a superb drive past goalkeeper Derek Soutar.

Aberdeen lost Lee Mair to injury at half-time, Foster being his replacement, while Hearts made a tactical change by bringing on Andrius Ksanavicius for Andrew Driver.

The changes did little to lift the game out its tedium, although Smith forced a good save out of Banks with a curling effort from 20 yards.

Velicka sent a drive wide and Palazuelos sent a drive straight at Soutar at the other end.

Dons substitute Craig Brewster followed a fine turn in the box by sending the ball into Banks' arms from 10 yards as the sides had to settle for a share of the points.

Aberdeen: Soutar, Hart, Diamond, Severin, Mair (Foster 46), Nicholson, McNamara, Clark (Brewster 82), Jamie Smith, Lovell (Maguire 61), Mackie.
Subs Not Used: Langfield, Miller, Daniel Smith, Stuart Smith.

Booked: Mackie.

Goal: Nicholson 19.

Hearts: Banks, Neilson, Zaliukas, Berra, Wallace, Palazuelos, Jonsson, Stewart, Ivaskevicius (Mikoliunas 74), Velicka (Makela 90), Driver (Ksanavicius 46).
Subs Not Used: Kurskis, Karipidis, Goncalves, Cesnauskis.

Booked: Neilson, Ivaskevicius, Zaliukas, Palazuelos.

Goal: Stewart 45.

Att: 13,134

Ref: I Brines