Roberto Martinez's side might have been worried for a time early in the first half as they were kept at bay in the League A encounter, but Eden Hazard's opener from the penalty spot was followed by a Lukaku strike just 121 seconds later.
While Belgium were not wholly convincing, their lead never looked threatened and they spent the second half on the front foot, chasing a further goal that eventually arrived through Lukaku again.
Even at three goals down, Iceland were able to retain at least some respectability in response to a weekend showing when Group 2 rivals Switzerland ran out 6-0 winners with embarrassing ease.
Iceland made the early running, perhaps keen to atone for Saturday's humbling, but the visitors slowly turned the screw and opened the scoring from the spot with their first real opening, Hazard converting after Sverrir Ingi Ingason tangled with Lukaku.
And Belgium quickly doubled their advantage. Hannes Thor Halldorsson parried Vincent Kompany's header, but Lukaku prodded the rebound just over the line for a second goal in three minutes.
The hosts came out rejuvenated at the start of the second half but, once again, it did not last and Thomas Meunier should have added a third when he turned Hazard's pinpoint cross wide. The same man struck the foot of the post shortly afterwards when he looked destined to score, dashing into the area on the right and shooting low past the goalkeeper.
Gylfi Sigurdsson belatedly stung the palms of Thibaut Courtois with Iceland's first effort of note, yet there never appeared a real danger of Belgium ceding their comfortable advantage and Lukaku beat Ingason to a low cross to net the third.
What does it mean: A two-horse race
After reaching the last four in Russia, Belgium will no doubt see this as a competition they can win. And just two games into the group, there appears little doubt that Martinez's men are battling with Switzerland. As Iceland struggle to deal with the attacking quality of each opponent in this part of the Nations League's top tier, Belgium v Switzerland next month will be key.
Pat on the back: Belgium's streaky striker stars
Captain Hazard caused Iceland problems out wide, but it was Lukaku's pace, power and movement that the hosts really could not handle. The Manchester United forward continues to deliver on the international stage, netting his 19th and 20th Belgium goals in his last 17 games, and relieved pressure as needed on this occasion.
That's 0-3 !!
2 goals in 1 #NationsLeague game
43 goals in 77 @Belgianfootball matches
@RomeluLukaku9 #REDTOGETHER #ISLBEL #NationsLeague pic.twitter.com/lYSLUnux5g — Belgian Red Devils (@BelRedDevils) September 11, 2018
Boot up the backside: Ingason hinders hosts
Iceland started strongly after the debacle of their defeat in Switzerland, so the last thing they needed was a foolish defensive error. Ingason's challenge on Lukaku gave the referee little option but to point to the spot. Belgium were slightly off-colour and required Iceland to make mistakes, but Ingason let the visitors off the hook and was again at fault for Lukaku's second, as the United striker overpowered him too easily.
That crunch Belgium v Switzerland clash is next up in this group, with Iceland looking for revenge against the latter in Reykjavik three days later.