The home side were not finished though, and added a third through Messi in second-half stoppage time as Ernesto Valverde's side claimed all three points with a three-goal success.
Messi had the chance to send Barcelona ahead inside the first three minutes of the contest, but the Argentine just missed the Alaves post with an effort from inside the penalty box.
Messi turned provider in the sixth minute when he picked out Jordi Alba with an excellent pass, and the left-back's effort smashed into the side-netting as Barcelona started on the front foot.
Messi then found Luis Suarez with a sensational pass inside the Alaves box, but the Uruguay international could not gather the ball under his spell, with the away side escaping another dangerous moment.
Barcelona struggled in the period that followed, and aside from a Dembele effort - which drifted harmlessly wide of the post - Alaves were quite comfortable approaching the 30-minute mark.
Messi came within inches of breaking the deadlock in the 38th minute, however, with the Argentine's excellent free kick striking the crossbar, before Ousmane Dembele brought a smart save from Fernando Pacheco moments later.
Luis Suarez's best chance of the first half arrived late on when he lifted the ball over Pacheco on the run, but Alaves centre-back Guillermo Maripan was across to clear behind with his head.
Coutinho came off the Barcelona bench at the interval, but it was Alba who had the home side's first chance of the second period, with the left-back racing into the Alaves box before bringing a smart save from Pacheco.
Messi then struck over the Alaves crossbar just before the hour as Barcelona continued to search for the opening goal of the match.
Finally the breakthrough came in the 64th minute, with Messi's low free kick finding a route into the back of the net as Alaves were handed a huge blow ahead of the final 25 minutes.
Messi almost put the game beyond Alaves in the 66th minute when he curled one towards the top corner, but the woodwork once again came to the rescue of the away side.
Pacheco made another smart save to keep out Suarez in the 73rd minute, before Arthur came on for his Barcelona debut in the home side's second change of the match.
Coutinho put the match beyond Alaves in the 83rd minute when the Brazilian danced into the penalty area before finding the back of the net with a wonderful strike.
Messi came close to adding a second late on when he broke into a shooting position, but Pacheco made another excellent save.
Messi was not to be denied, however, and made it 3-0 in the closing moments with a simple pass into the bottom corner from a brilliant Suarez assist.
BARCELONA (4-3-3): Ter Stegen; Semedo (Coutinho 46'), Pique, Umtiti, Alba; Rakitic, Busquets (Vidal 85'), Roberto; Messi, Suarez, Dembele (Arthur 77')
ALAVES (4-3-3): Pacheco; Martin, Laguardia, Maripan, Duarte; Manu, Wakaso, Torres (Borja 68'); Jony (Baston 68'), Sobrino (Burgui 71'), Ibai Gomez