The Red Devils, who will cross the boarder into France as one of the tournament favourites, scored twice in quick succession in the final 20 minutes of the match to turn the game back in their favour.
Manager Marc Wilmots was given one final chance to run the rule over his players, but for large parts it was a frustrating evening for Belgium at the King Baudouin Stadium until they eventually clicked into gear.
It took less than three minutes for the hosts to open the scoring, as some poor defending gave Romelu Lukaku the chance to put his foot through the ball right on the edge of the box.
Orjan Nyland was well positioned to keep the powerful shot out down the middle, but he allowed it to squirm through his grip to gift Belgium the tamest of opening goals.
The Red Devils continued to dominate the opening quarter of the match in terms of possession in dangerous areas but, a wayward Axel Witsel shot aside, there was far too little in terms of end product.
That theme continued until 22 minutes in when Norway hit back from their first meaningful attacking move of the match, with Radja Nainggolan the man at fault as his error allowed Stefan Johansen to play in Joshua King with a smart reverse pass.
Despite the angle being against the Bournemouth striker somewhat, King coolly tucked the ball across the body of Thibaut Courtois into the far corner of the net for his sixth goal on the international stage.
A competitive remainder to the opening 45 minutes followed, although it was the world's 51st-ranked side who came closest to bagging a second when Veton Berisha made the most of the Belgian backline falling asleep.
The Greuther Furth youngster managed to cut inside and fire away a shot, which forced Courtois into making the first save of any note from either goalkeeper on the brink of half time.
While Wilmots's men made a bright start to the first half, it was Norway's turn to catch their opponents cold in the early stages of the second as they edged ahead through Berisha.
Nyland more than made up for his earlier error when keeping out Witsel and, more impressively, Kevin De Bruyne from close range in a double stop, allowing the visitors to counter and take the lead through a well-struck Berisha drive that left Courtois rooted.
Chasing a goal for the first time, Wilmots turned to Marouane Fellaini - nursing an injury heading into this match - on the hour mark as he looked to go more direct.
The alteration did not seem to make all that much difference at first, though, as Norway barely had to break a sweat to keep the hosts' clear-cut chances to a minimum.
That all changed 20 minutes from time when Belgium finally upped the ante a little and were rewarded with a leveller - Eden Hazard getting the smallest of touches to the ball as he glanced De Bruyne's cross into the far corner.
Just three minutes later the Scandinavian outfit were behind after a corner was this time nodded home by substitute defender Laurent Ciman from close range.
A raft of substitutions in the closing stages disrupted the flow of the match, meaning that the World Cup 2014 quarter-finalists could easily see things through to head into the Euros on a high.
For Norway, on the other hand, they were ultimately unable to follow up their impressive 3-2 win over Iceland with another victory as they now switch attention to their World Cup qualification campaign.