The two leaders shook hands and shared smiles as they met and gave brief statements before heading in for the talks, held at a university campus on the Pacific port city's Russky island.
Both said they were looking to strengthen historic ties that date back to the Soviet Union's support for the founder of North Korea, Kim's grandfather Kim Il Sung.
Praising the two countries' "long friendship and history", Kim said he hoped to turn the modern relationship with Moscow into a "more stable and sound one".
"As the world is focused on the Korean peninsula, I think we will hold a very meaningful dialogue," Kim said.
Putin said the visit would give a boost to bilateral ties and help Moscow understand "what Russia can do to support the positive processes that are currently taking place" in the peninsula.
Putin also said there was "a lot to do" to develop economic relations between the two countries.
The meeting was Kim's first one-on-one talks with another head of state since returning from his Hanoi summit with US President Donald Trump, which broke down without a deal on North Korea's nuclear arsenal in February.
- North Korean labourers - Among the issues likely to be on the table is the fate of some 10,000 North Korean labourers working in Russia and due to leave by the end of this year under sanctions.
Labour 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.
Kim, whose government has told the United Nations it is facing food shortfalls this year, will also be keen to see Moscow continue or boost its aid.
Russia has provided some $25 million in food aid to North Korea in recent years, according to the Kremlin. One delivery in March saw more than 2,000 tonnes of wheat supplied to the port of Chongjin, news agency TASS reported.
For Putin, the summit is a chance to push Russia's agenda of opposing US international influence.
In an interview with China's official People's Daily published on Thursday, Putin lashed out at "countries claiming sole global leadership".
"They carelessly trample on the norms and principles of international law, resort to blackmail, sanctions and pressure, and try to force their values and dubious ideals on entire countries and populations," said Putin, who is heading to China after the talks for another summit.
Since March 2018, the formerly reclusive North Korean leader has held four meetings with Chinese President Xi Jinping, three with South Korea's Moon Jae-in, two with Trump and one with Vietnam's president.
At the meeting with Trump in Hanoi, the cash-strapped North demanded immediate relief from sanctions, but the talks broke up in disagreement over what Pyongyang was prepared to give up in return.
North Korea last week launched a blistering attack on US Secretary of State Mike Pompeo, insisting he be removed from the negotiations just hours after announcing it had carried out a new weapons test.
Pompeo said on Wednesday he expected "bumpy" talks ahead with Pyongyang but that he still hoped to reach a potentially landmark denuclearisation deal.
- Soviet-era allies -
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 Russia denies.
Moscow was a crucial backer of Pyongyang for decades and their ties go back to the founding of North Korea, when the Soviet Union installed Kim Il Sung as leader.
The USSR reduced funding to the North as it began to seek reconciliation with Seoul in the 1980s, but Pyongyang was hit hard by its demise in 1991.
Soon after his first election as Russian president, Putin sought to normalise relations and met Kim Jong Il -- the current leader's father and predecessor -- three 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.
While ties between Moscow and Pyongyang have remained cordial, the last meeting between their leaders 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. (AFP)
