The dispute over the fate of four Russian-held islands known as the Northern Territories in Japan and the Southern Kurils in Russia is in the spotlight ahead of Putin's planned visit to Japan next year.
The status of the four islands, seized by the Soviet Army at the end of World War II, has soured relations between Moscow and Tokyo for nearly 60 years and prevented them from signing a formal peace treaty.
In a meeting after the conclusion of a summit of the Asia-Pacific Economic Cooperation forum, Koizumi told Putin that it was clear that signing a peace treaty and bolstering relations was in the "strategic interests" of both sides, a Japanese government official said.
"Prime Minister Koizumi ... strongly urged that it is the responsibility of the two leaders to tackle the historic issue of concluding a peace treaty," he said.
Putin replied by saying he thought it was necessary to resolve various issues and conclude a peace treaty, and the two leaders agreed to continue talks on various levels including mutual visits by their foreign ministers, the official said.
But the leaders did not go into details about past circumstances related to the dispute, the official said.
There was also no mention of a specific date for Putin's planned visit to Japan next year, which is the 150th anniversary of the first trade treaty between Russia and Japan, he said.
Foreign Minister Sergei Lavrov said last Sunday that Moscow would honor a 1956 agreement, which it says obliges it to return the two southernmost islands.
But Japan wants all four back and has shown no interest in a partial solution of the territorial problem.
Besides the territorial dispute, Koizumi and Putin, who met for the first time since June, also discussed North Korea.
The two leaders agreed to cooperate to make North Korea understand the importance of six-way talks over Pyongyang's nuclear weapons programs and to aim for an early resumption of the six-country talks, the Japanese official said.
North Korea refused to attend talks in September, and U.S. President George W. Bush's goal at the APEC summit was to rally the allies to persuade Pyongyang to agree to a new round of six-party talks by the end of the year or early next year.
The nuclear crisis began in October 2002 when U.S. officials said North Korea admitted to working on a secret program to enrich uranium for weapons. North Korea denies having such a program.
A Message from The Moscow Times:
Dear readers,
We are facing unprecedented challenges. Russia's Prosecutor General's Office has designated The Moscow Times as an "undesirable" organization, criminalizing our work and putting our staff at risk of prosecution. This follows our earlier unjust labeling as a "foreign agent."
These actions are direct attempts to silence independent journalism in Russia. The authorities claim our work "discredits the decisions of the Russian leadership." We see things differently: we strive to provide accurate, unbiased reporting on Russia.
We, the journalists of The Moscow Times, refuse to be silenced. But to continue our work, we need your help.
Your support, no matter how small, makes a world of difference. If you can, please support us monthly starting from just $2. It's quick to set up, and every contribution makes a significant impact.
By supporting The Moscow Times, you're defending open, independent journalism in the face of repression. Thank you for standing with us.
Remind me later.