Portugal boss Carlos Queiroz chose the same starting XI of the one used three weeks ago against the Faroe Islands and it proved to be a winning formula as his team were in control of the game from the off.
The away team had their first chance on goal in the fifth minute. Portugal's corner caused huge confusion in the Maltese box, Pepe received the ball but his shot went over the bar.
Just one minute later, a curious situation: the power at the Ta' Qali Stadium went down and the game had to be stopped for almost 10 minutes before the required conditions could be met.
Malta then surprisingly started pushing forward and it appeared as though they were the in the driving seat but it would be Portugal to break the deadlock. In the 25th minute, Nani served Bosingwa down the right, the Chelsea man tried to cross to Hugo Almeida but Said got the last touch to send it past his own keeper.
Portugal should have enlarged their lead in the 33rd minute, when Hugo Almeida headed to Simão after a cross from Bosingwa but the Atlético de Madrid winger could not hit the ball and Malta cleared the danger.
Four minutes later, Nani tried his luck with a well-placed shot but Haber made a good flying save to touch away his effort.
The game finally reached the half-time mark with the away side leading 1-0. Portugal were far from their best, but it proved to be more than enough for Malta in the first 45 minutes.
The second period began in the same manner as the first with Portugal trying to find the net and Malta presenting an ultra-defensive system.
Portugal scored their second of the night in the 60th minute. A very long ball played Hugo Almeida through, who, with only the keeper to beat, fired home a powerful shot with his left foot.
On 71 minutes, Portugal scored once again. Deco found Nani alone in the right side of the box, whose shot was denied by Haber but Simão Sabrosa was there to tap in the rebound.
On 78 minutes, Deco played Nani through, who made no mistake with a low yet strong finish. Nani was in offside position, yet the assistant referee failed to see it and the game was thus 4-0 for Portugal.
It was a well-deserved win for Portugal, who are now leading Group 1 after Sweden and Denmark shared points with Albania and Hungary respectively.
Malta: Justin Haber; Roderick Briffa, Brian Said, Luke Dimech, Shaun Bajada, Gilbert Agius (Ryan Fenech 80'), Kevin Sammut, Jamie Pace, Ivan Woods (George Mallia 58'), Michael Mifsud, Terrance Scerri (Etienne Barbara 69').
Portugal: Quim, Bosingwa, Pepe, Ricardo Carvalho, Antunes,
Raul Meireles, Nani, Carlos Martins (Maniche 62'), Deco, Simão Sabrosa
(João Moutinho 74'), Hugo Almeida (Nuno Gomes 76').
Malta 0-4 Portugal
0-1 Brian Said 25' (OG)
0-2 Hugo Almeida 60'
0-3 Simão Sabrosa 71'
0-4 Nani 78'