An economist by training, Norway's former prime minister, who will replace current secretary general Anders Fogh Rasmussen on October 1st, has never had any particular fondness for defence or security matters.
But a decade in office has left the 55-year-old with a strong international network and honed his skills as a cross-border negotiator.
Norway's Labour Party head is the first NATO secretary general from a country bordering Russia and his friendly ties with Moscow could be an important asset as the Crimea crisis revives tensions not seen since the days of the Cold War.
During his tenure as prime minister, Norway and Russia signed key agreements on the delineation of their frontier in the Barents Sea and on visa exemptions for their border populations.
"Stoltenberg's and Norway's experience as a neighbour of Russia will surely come in handy," the respected Norwegian daily Aftenposten commented recently. "But the decision on what kind of relationship the West ought to have with Russia is made in other forums than the NATO system," the newspaper added in an oblique reference to the European Union and, above all, the United States.
As a young man, Stoltenberg was vehemently opposed to NATO and the European community, two organizations that he eventually came to support.
As a long-haired teenager, he threw stones at the US embassy in 1973 in reaction to Washington's bombardment of Haiphong in North Vietnam.
Twelve years later, he assumed the reins of Labour Youth, at a time when it advocated a Norwegian exit from NATO. It was on his watch that the organization eventually rallied to the cause of the Atlantic Alliance.
"It appears that his radical notions have been merely diluted with age – but not altogether discarded," a commentator at The Wall Street Journal wrote recently.
The conservative newspaper reminded its readers that as a minister, Stoltenberg took part in an Oslo-Paris bicycle relay in 1995 to protest French nuclear testing at Mururoa atoll.
Born into a political family — his father was minister of defence and then of foreign affairs, his mother a deputy minister — he also devoted the majority of his career to politics.
After joining parliament in 1991, the tall, blue-eyed Norwegian rose rapidly through the political ranks, becoming minister of energy and then of finance, before being named the country's youngest prime minister in 2000, the day after his 41st birthday.
He only kept that position briefly, but returned to power in 2005 and stayed on at the head of government until October last year.
Under his leadership, the Scandinavian country participated in the war in Afghanistan and contributed to the air strikes against Libya's Moamer Kadhafi.
Norway, traditionally pacifist but with strong Atlantic ties, is one of the few NATO countries that has increased its defence budget in recent years.
Enjoying a high level of popularity as prime minister in his own country, Stoltenberg also received international praise when he called for "more democracy" and "more humanity" after extremist Anders Behring Breivik killed 77 people on July 22nd, 2011.
He also appeared to be a man of the people in a pre-election stunt in 2013 where he posed as a taxi driver in order to hear the views of ordinary voters. However the stunt backfired when it later emerged that the Labour Party had recruited and paid some of the passengers.
The married father of two cut his teeth on difficult negotiations in the past. These days he is so skilled at the art of compromise that some accuse him of being adverse to conflict.
"Nobody can consider Jens Stoltenberg a hawk on security policy," said Gunnar Stavrum, a commentator at online newspaper Nettavisen.
"The choice of Jens Stoltenberg shows that after a period of intensified international conflict, the big members of NATO want a secretary general who is prepared to compromise."