Mr Abe's visit to the Russian capital is the first by a Japanese government chief in a decade.
Russia and Japan's failure since the 1950s to agree a World War II peace treaty owing to the dispute over the Pacific Kuril islands chain has held up full potential of bilateral ties.
Since returning to power in December, Mr Abe has made a priority of improving relations with Russia and given rise to cautious hope by backing the resumption of stalled talks on a solution.
"I am sure today we will talk about our key problem, the peace treaty between Russia and Japan," Mr Putin told Mr Abe in unusually frank opening remarks as talks got underway at the Kremlin.
Without directly referring to the islands dispute, Mr Abe hailed the development of relations with Russia during Mr Putin's 13-year domination of the country but admitted more needed to be done.
"The potential for cooperation has not been unlocked sufficiently and it is necessary to increase the cooperation between our countries as partners," he said in comments translated from Japanese.
Mr Abe has made clear he wants to build a strong personal relationship with Mr Putin as the basis for solving the two countries' problematic relations.
"I will work on boosting Japan-Russia relations so that this visit will mark a restart in stalled negotiations over a peace treaty," Mr Abe told reporters before leaving Tokyo.
The pair are expected to release a joint statement confirming they would restart territorial talks, a Japanese government source told Kyodo News.
Kuril islands dispute
The last such top-level official visit was by then prime minister Junichiro Koizumi, who travelled to Moscow to meet Putin in January 2003.
Former prime ministers Yasuo Fukada and Taro Aso visited in 2008 and 2009 for shorter, lower-level trips.
Mr Abe is being accompanied by a business delegation of 120 people, the biggest ever such group to join a Japanese prime minister on a visit to Russia.
Japan is particularly interested in increasing its import of Russian energy resources as it seeks to diversify supplies in the wake of the Fukushima nuclear disaster.
Russia's trade with Japan reached $32 billion in 2012. But Russia, despite its size and proximity, was only Japan's 15th most important trading partner, in a sign of the unrealised potential of relations.
The dispute surrounds the southernmost four of the Kuril islands - known in Japan as the Northern Territories - which have been controlled by Moscow since they were seized by Soviet troops at Stalin's behest in 1945 at the end of World War II.
The Kremlin said in a statement that Russia believed that "dialogue in the interests of arriving at a mutually acceptable solution must be held in a calm, respectful atmosphere."
Yet there remains little hope of an immediate breakthrough, with Tokyo insisting the four islands currently inhabited by around 16,500 Russians are its territory and Moscow showing no hint of a compromise.
Russian Prime Minister Dmitry Medvedev has twice visited the island of Kunashir, called Kunashiri in Japan, infuriating Tokyo.
Medvedev's first visit to the island, which juts out past the northeastern tip of Japan's Hokkaido island, in November 2010 - when he still held the post of president - was condemned by Tokyo as an "unforgivable outrage".
One solution mooted in the past could involve Russia ceding control of the two smallest islands of Shikotan and Khabomai and keeping the much larger Kunashir and Iturup (know as Etorofu in Japan).
But even this would require massive concessions from both sides that would be unpalatable for nationalists.
After Russia, Mr Abe is expected to visit Saudi Arabia, the United Arab Emirates and Turkey for talks with leaders there.