Barcelona, who went into the game on the back of the disappointing 2-1 loss to Deportivo, started the clash at the Camp Nou in positive fashion but it was the visitors who managed to open the scoring on the 29th minute from a set-piece.
Daniel Parejo whipped in a lovely corner from the right and Eliaquim Mangala, on-loan from Manchester City, produced a towering header that found the top-left corner.
The Catalans were back on lovely terms just six minutes later when Luis Suarez raced through unmarked into the box after a quick throw from Neymar had caught Los Che off guard, and the Uruguayan slotted a neat finish into the bottom-right corner.
A huge moment then came about right on the stroke of half-time when Mangala pulled Suarez down in the box, resulting in the defender being given his marching orders and the hosts getting a penalty.
Messi confidently stepped up and smashed the spot-kick right down the middle, giving the home side a 2-1 lead with just seconds left in the opening period.
However, the action wasn't over yet and Valencia went down the other end straight from the restart and levelled things up when Munir, who is on-loan from Barcelona, tapped in from close-range after a good lay-off from Jose Gaya.
Into the second-half and Luis Enrique's men almost took the lead when Neymar was one-on-one with goalkeeper Diego Alves, but the Brazilian's effort was smartly saved by the legs of the shot-stopper.
But, just moments later, Barca did score a third when Messi showed a good turn of pace in the box before firing a powerful effort inside the near-post.
Valencia still posed a threat when coming forward, despite being down to 10-men, and Munir should have done a lot better when he was played through down the left flank.
The Spain international raced into the box but his attempted cut-back onto his right foot was well read by the recovering Pique, who managed to scramble the ball away.
Barcelona did make sure of all three points in the 89th minute when substitute Andre Gomes placed the ball into the top-right corner after some neat build-up play from the hosts.
The victory leaves Enrique's side second in the table but they cut the gap to leaders Madrid to just two points - although the latter do have a game in hand on their rivals.