The Argentine maestro, who injured his hamstring in the 2-2 first leg in Paris last week, clambered off the bench just after the hour-mark to completely change the direction of the match and to have a major hand in Barcelona's equalising goal.
Tito Vilanova's men were able to get themselves through to the final four for the sixth straight season by virtue of the away goals rule after the two-legged tie finished 3-3.
Javier Pastore put PSG deservedly ahead five minutes into the second half when he received a neat ball from Zlatan Ibrahimovic before drawing wide from the goal and then sliding it over Victor Valdes with his left foot.
PSG had a couple of decent chances to put the Catalan giants away but enter Messi, who had a key impact after replacing Cesc Fabregas in the 62nd minute.
The Nou Camp crowd and his teammates lifted and he constructed the levelling goal when he dazzled the PSG defence with a barnstorming run before picking out David Villa just inside the area for the Spanish international to tee it up for Pedro who powered home in the 71st minute.
2012/13 UEFA Champions League quarter-final - second leg
Nou Camp, Barcelona - 96,022