"It's more about his relations at a state leader level," Bernt Aardal, Professor of politics at Oslo University told The Local. "There has been a very close relationship between Stoltenberg and Merkel for a long time. They understand each other. And his relationship with [US President Barack] Obama seems to be both cordial and relatively close."
The world only learned of Stoltenberg's impressive skills as a speaker following Norway's twin terror attacks in 2011.
His call to "answer hatred with love" struck a chord all over the world, with its stark contrast to the reaction of the United States after the attack on the twin towers in 2011.
But in Norway, Stoltenberg has dominated the political landscape for more than a decade.
Even now, nearly ten years after he started his second stint as prime minister, he rivals the Conservative leader and current Prime Minister Erna Solberg in national popularity polls.
"He's considered to be a very likeable person. He's good with people," Aardal said. "If you've managed to leave your office almost as popular as you've entered it, I think that says something."
Stoltenberg is certainly no left-wing fire-brand. He threw his public support behind the US War on Terror after the attacks on the twin towers in 2001, arguing that "it is also in our interests to hit back against such attacks."
He backed the decision to send Norwegian troops to fight in Afghanistan, and sent Norwegian jets to aid the rebel side during the civil war in Libya.
While he was Prime Minister from 2005 to 2013, he steadily increased Norway’s defence spending, giving it one of Nato's highest per capita defence expenditures.
The same goes for his economic and social policies. His economist's training puts him firmly on the pro-business wing of Norway's Labour Party, even though he has never wavered in his commitment to the Nordic social democratic model.
"He's a pragmatic politician. He's not a strong ideologue," Aardal said. "He has actually been very good at political maneuvering and being prime minister of a coalition government for eight years has also given him experience of trying to build consensus but at the same time being a strong leader."
In Norway, Stoltenberg's suitability for one of the top jobs in international politics is so obvious that he has been fighting rumours he is about to step down as leader of the Labour Party from the moment he lost the election last September.
Story continues below…
The path has been well-trodden before him. Gro Harlem Brundtland's glittering international career after stepping down as Norway's Prime Minister in 1996 now completely overshadows her achievements in Norway.
Stoltenberg's own father, Thorvald, a former Norwegian Foreign Minister, went on to serve both as UN High Commissioner for Refugees and as UN special representative on the former Yugoslavia.
But what's for certain is that while Jens Stoltenberg sails on to further glories, his departure from Norwegian domestic politics will come as a hard blow for the Labour Party.
In that at least, Merkel has done Norwegian PM Erna Solberg, her fellow fighter on the European centre-right, something of a favour.