Rayo could not handle the partnership which accounted for all three goals - Messi netting twice after Villa had opened the scoring.
The visitors remain in mid-table but can feel satisfied with an enterprising display which saw them create numerous chances before Raul Tamudo grabbed a late consolation.
They would have been beaten by a greater margin, however, had Barca made more of the plethora of chances which they carved out.
Confidence was clearly high in the Azulgrana ranks following their 4-0 demolition of AC Milan in the Champions League in midweek - a result which saw them overturn a 2-0 first-leg deficit and power through to a last-eight meeting with Paris St Germain.
They could have opened the scoring after five minutes only for Messi to uncharacteristically fluff his lines.
Having been presented with an open goal by Cesc Fabregas, the Argentinian dallied on the ball and allowed the Rayo defence to get back and avert the danger.
Messi did rather better three minutes later with a curling free-kick which struck the bar with visiting goalkeeper Ruben a spectator.
Rayo immediately went up the other end but their penalty claims after Alejandro Dominguez went down theatrically in the penalty area under a challenge from Javier Mascherano were waved away.
Roberto Trashorras tested Barca stand-in goalkeeper Jose Pinto - regular number one Victor Valdes is suspended - in the 22nd minute before the hosts went in front.
Messi cleverly beat his marker on the halfway line before feeding Villa and the Spain international made no mistake with a clinical right-footed shot into the top corner.
The long-standing rumours that Messi and Villa do not get on appeared even more far-fetched when they combined again five minutes before half-time.
Having pulled down Sergio Busquets' raking ball, Villa played in Messi who swept his shot past Ruben. It was the 18th league match in succession in which Messi has scored.
Villa ought to have made it 3-0 before the break but dragged his shot past the far post after being played in by Fabregas.
Dani Alves, a 23rd-minute substitute for the injured Adriano - the Brazilian was later ruled out for up to six weeks with a hamstring injury - was a constant menace for the Rayo defence and he lashed a shot against the post shortly after the restart.
Alexis Sanchez was next to try his luck, after 54 minutes, but could only pull his shot woefully wide having been set up by a combination of Messi and Alves.
A third Barca goal seemed a matter of time and it arrived after 57 minutes on the counter-attack.
Barca cleared a Rayo corner to leave Villa and Messi with a two-on-two situation. Villa's pass took out one Rayo defender and Messi outsprinted the other - Anaitz Arbilla - before a trademark clip over the advancing Ruben.
Rayo pulled one back with 20 minutes to go as former Espanyol striker Tamudo, whistled on to the field as a substitute for Andrija Delibasic, netted within a minute of his introduction, turning home a low Piti centre.
Lass Bangoura then forced Pinto to scramble across his line with a shot which ended up in the side-netting as Rayo threatened an unlikely comeback.
Barca swiftly reasserted their superiority and ought to have added further gloss to the scoreline but Messi was denied by a wonderful Ruben save before the FIFA World Player of the year scooped a dainty shot on to the roof of the net in injury time.