Kim's Russia trip comes less than three months after he travelled to China, which was his third trip there in a year, capping his busiest schedule of foreign travel in his 17 years of power.
The North owes its political survival to both countries. For decades Moscow was its main ally, providing military and economic support before the collapse of the Soviet Union in the early 1990s. Since then the North has realigned its foreign policy toward China.
This latest trip could be an attempt to balance China's influence by forging closer ties with Russia, says Reuters.
The talks ended with a Kremlin announcement that North Korea was ready to resume nuclear dialogue without preconditions and abandon atomic enrichment and testing once the talks begin.
But both the United States and South Korea -- who along China and Japan make up the other countries in the so-called six-party nuclear talks -- dismissed the proposal as nothing new.
"If it's true, (it's a) welcome first step, but far from enough ... to resume the six-party talks," US State Department spokeswoman Victoria Nuland told reporters.
South Korean officials demanded that the North abandon its nuclear programme before assuming negotiations on the potential lifting of sanctions and provision of international aid for the impoverished republic, according to Sin Chew Jit Poh.
"I am full of positive feelings. The meeting was substantive and open," Medvedev said after the meeting.
He told journalists that North Korea supported a planned pipeline to carry Russian gas supplies to South Korea through the North, a route that would allow Moscow to reach new energy-hungry Asian markets.
After a long-lasting freeze in six-party talks on the North Korean nuclear programme, a Kremlin official said Pyongyang was ready to impose a moratorium on nuclear testing and processing if the discussions resume, informs Bangkok Post.