Liu Jianchao and Kishida spoke at the prime minister's office. Afterwards, Liu talked briefly to reporters.
"We are promoting a strategic and mutually beneficial relationship between China and Japan," Liu said. "We place importance on the challenges and differences between the countries."
Kishida reportedly echoed Liu's sentiment on dealing with issues through dialogue.
Liu is currently the head of the International Department of the Chinese Communist Party's Central Committee. Observers say it is possible he may become China's next foreign minister, succeeding Wang Yi, who currently holds the post.
Liu also met with Japan's Foreign Minister Kamikawa Yoko and leaders of the ruling and opposition parties.
Beijing correspondent Nakamura Genta says China had a goal for the visit.
"It appears that Beijing may be trying to repair its relationship with Japan that, as of now, remains sour," he adds.
Tensions between Japan and China
Chinese vessels have repeatedly breached territorial waters around the Senkaku Islands. Japan controls the islands. The Japanese government maintains the islands are an inherent part of Japan's territory. China and Taiwan claim them.
In August 2023, Beijing responded to Japan's discharge into the ocean of treated and diluted water from the Fukushima Daiichi nuclear power plant by banning imports of Japanese marine products.
Wary of stronger ties between allies
Xi Jinping's leadership is trying to move toward dialogue with Japan, partly because it is wary of Japan-US ties that appear to be aimed at deterring China. Beijing also recognizes that if South Korea joins the Japan-US alliance, its activities in the East China Sea and the Sea of Japan could be constrained.
Nakamura says Beijing is also watching the US presidential election.
"If Donald Trump wins, his 'America First' agenda could destabilize ties with Japan, South Korea and other allies," he adds. In anticipation, Beijing may be "trying to close the distance with Japan while it still can."
Liu, the next foreign minister?
There has been talk about Liu becoming China's next foreign minister, a role that has seen some upheaval during Xi's leadership. Some experts say his visit to Japan reinforces that possibility, but Nakamura says it is hard to know at this point.
"Liu is considered a strong candidate," he adds.
China is trying to soften its image with the US and Europe. Since it is seeing declining foreign investment, it is hoping to improve relations with its counterparts. Many who have met Liu say he is more informal and engaging than other Chinese officials.
"If Liu is appointed, it would signal a departure from the abrasive 'wolf warrior' diplomacy that has come to symbolize China's assertive posture under Xi Jinping," Nakamura says.
In January, Liu met with US Secretary of State Antony Blinken and UN Secretary General Antonio Guterres. It is rare for an official in his post to meet with high-ranking foreign officials. Many see it as Liu taking on a role as shadow minister.
Managing relations with the West?
Even though Beijing appears to want to mend ties with Washington, it also invited Russian President Vladimir Putin for a visit earlier this month, which could send a confusing message to the West.
Nakamura says it should be noted that in his talk with Kishida, Liu still took a hard stance.
"When discussing the treated and diluted water discharge, he used the phrase 'nuclear contaminated water' in line with Beijing's typical tone. So, even with Liu's more amiable approach, it will not be easy to assuage the West's concerns, even as foreign minister," Nakamura adds.