Don't forget - Goal.com Champions League Manager 2008-2009 is ready for registration. Sign up now at http://fantasy.goal.com - it's absolutely free and there are great prizes to be won in the hottest managerial game of the new season!
The Argentinian toe-poked home from close range after a huge mistake from Andriy Pyatov to cancel out Ilsinho's opener and he then netted a superb winner with virtually the last kick of the game.
In a very tight encounter in the Champions League, the home side looked set to be heading for a hard-fought victory, but they were to be denied as the Blaugrana's late pressure eventually told.
At the final whistle, the home team's frustrations showed as Mircea Lucescu refused to shake hands with Pep Guardiola following a spat between Brandão after Barça's equaliser.
It was the giant Brazilian that stood out for the whole game as he showed everything that he was capable of with a display that could well have won him a host of new admirers.
His huge physique belied his incredible speed, but he could also mix it in the tackle as well as proving to be cynical with his fouls and soft with his dives.
But his performance summed up a very hard-working showing by a Shakhtar side that looked to have worked out how to beat their hosts by not allowing them any space in midfield and by quickly closing them down whenever they looked to create.
Guardiola obviously recognised that Shakhtar would be hard in midfield as he put Seydou Keita in with Touré Yaya, while Carles Puyol was preferred at left-back in place of the struggling Éric Abidal and Thierry Henry, Samuel Eto'o and Andrés Iniesta former the front three.
Barça did start brightly and before their hosts organised themselves, Henry was picked out through the middle and he should have scored but was denied by Andriy Pyatov.
Despite Shakhtar having their fair share of the ball it was not until eight minutes before the break that Víctor Valdés saw action for the first time when Alves' error allowed Brandão to break forward and pick out Luiz Adriano and he in turn found Ilsinho, but the keeper turned the shot superbly over.
There was little the Catalan custodian could have done six minutes later though when the home team did take the lead after some poor defending let them in through the middle.
A high ball forward was flicked on by Piqué and Ilsinho comfortably held off the challenge from Puyol before clipping the ball over the approaching Valdés.
It was quickly clear that Guardiola was unhappy with his players because Barcelona came out for the second half with a renewed vigour and had two glorious chances to draw level.
The first saw the keeper tip away Alves' free-kick from distance and the second came when Eto'o was released down the centre, but he stumbled at the crucuail moment and ended up prodding the ball wide.
It was not until Messi and Bojan Krkic came on that their speed and guile opened Shakhtar up as the pair combined for the opening goal even though a huge mistake from the keeper was required.
A low cross from the right by Krkic look relatively simple for Pyatov to claim but he spilt the ball and Messi toe-poked home from close range in the 86th minute.
Brandão was clearly unhappy with the celebrations as he challenged Krkic and Iniesta, but he would have been furious when Barça clinched a winner with the last kick of the game.
Xavi threaded a ball through the defence and Messi clipped it superbly over the keeper to send Barcelona back home with all three points that only a few moments earlier they lokoed like they were never going to claim.
Lucas Brown, Goal.com