Putin was keen to put Moscow forward as a player in a new global flashpoint – and it appears Kim was eager to take him up on the idea, during talks described by KCNA as "unreserved and friendly".
The two leaders greeted each other warmly, shaking hands and sharing smiles, at the start of meetings on an island off Vladivostok that lasted nearly 5 hours.
Putin, known for delaying meetings with international guests, was waiting for Kim when he emerged from his limousine.
During the talks, Kim said "the situation on the Korean peninsula and the region is now at a standstill and has reached a critical point," the Korean Central News Agency said.
He warned that the situation "may return to its original state as the US took an unilateral attitude in bad faith at the recent second DPRK-US summit talks", the agency added.
"Peace and security on the Korean peninsula will entirely depend on the US future attitude, and the DPRK will gird itself for every possible situation," KCNA quoted Kim as saying.
At those talks, cash-strapped Pyongyang demanded immediate relief from sanctions, but the two sides disagreed over what the North was prepared to give up in return.
Russia has already called for the sanctions to be eased, while the US has accused it of trying to help Pyongyang evade some of the measures – accusations Moscow denies.
Just a week ago, Pyongyang demanded the removal of US Secretary of State Mike Pompeo from the stalled nuclear talks, accusing him of derailing the process.
On Thursday, Putin emerged from the meeting saying that like Washington, Moscow supports efforts to reduce tensions on the Korean peninsula and prevent nuclear conflicts.
But he also insisted that the North needed "guarantees of its security, the preservation of its sovereignty".
"We need to... return to a state where international law, not the law of the strongest, determines the situation in the world," Putin said.
Kim said he hoped to usher in a "new heyday" in ties between Pyongyang and Moscow.
Both men said they were looking to strengthen ties that date back to the Soviet Union's support for the founder of North Korea, Kim's grandfather Kim Il-sung.
The two shared a lunch that included borscht, crab salad and venison dumplings, Russian news agency TASS reported.
The North Korean leader invited Putin to visit North Korea "at a convenient time" and the invitation was "readily accepted", KCNA said.
Kim, who arrived in Vladivostok aboard his armored train, was expected to stay until Friday for cultural events that Russian media have reported will include a ballet and a visit to the city's aquarium.
The meeting was Kim's first with another head of state since returning from his Hanoi summit with Trump.
It followed repeated invitations from Putin after Kim embarked on a series of diplomatic overtures last year.
Putin told reporters that he would fill in Washington on the results of the talks.
"There are no secrets here, no conspiracies... Chairman Kim himself asked us to inform the American side of our position," said Putin.
There were no concrete announcements or agreements in Vladivostok, but analysts said Thursday's meeting was valuable to both sides.
"For North Korea, it's all about securing another exit. China talks about sanctions relief but it doesn't really put it into action," said Koo Kab-woo, a professor at the University of North Korean Studies in Seoul.
"For Russia, North Korea is elevating it back to one of the direct parties, on the same footing as China."
North Korean laborers
Among the issues that were likely discussed was the fate of some 10,000 North Korean laborers working in Russia and due to leave by the end of this year under sanctions.
Labor is one of North Korea's key exports and sources of cash. Pyongyang has reportedly asked Russia to continue to employ its workers after the deadline.
Soon after his first election as Russian president, Putin sought to normalize relations with Pyongyang and met Kim Jong-il – the current leader's father and predecessor – 3 times, including a 2002 meeting also held in Vladivostok.
China has since cemented its role as the isolated North's most important ally, its largest trading partner and crucial fuel supplier, and analysts say Kim could be looking to balance Beijing's influence.
The last meeting between the leaders of Russia and North Korea came in 2011, when Kim Jong-il told then-president Dmitry Medvedev that he was prepared to renounce nuclear testing.
His son has since overseen by far the country's most powerful blast to date, and launch of missiles which Pyongyang says are capable of reaching the entire US mainland. – Rappler.com