A high-level Chinese envoy has returned from North Korea expressing optimism about the mounting nuclear crisis.
Mr Tang and Mr Kim discussed restarting the six nation talks
Tang Jiaxuan, who met North Korea's reclusive leader Kim Jong-il, said his visit had "not been in vain".
China is North Korea's closest ally and has publicly warned the North not to test another weapon.
Mr Tang was speaking to US Secretary of State Condoleezza Rice, who has stepped up calls for UN sanctions against the North to be fully implemented.
Ms Rice, who is in China as part of an Asian tour to rally support against North Korea, held talks with Chinese Foreign Minster Li Zhaoxing on Friday.
Ms Rice said the two discussed implementing UN sanctions imposed after Pyongyang's 9 October nuclear test and described the talks as "very fruitful".
The meeting comes amid concern North Korea is planning a second test, and reports that China has threatened to cut off vital oil supplies if it goes ahead.
The BBC's Rupert Wingfield-Hayes in Beijing says that behind the scenes there are signs China is starting to get tough with Pyongyang.
The threat to the oil supply demonstrates just how angry and frustrated China now is with its erstwhile friend and ally, our correspondent says.
On Thursday a North Korean official hinted that another test could take place.
The deputy head of North Korea's foreign ministry, Li Gun, speaking on ABC TV in the US, said a second test would be "natural" and that the US should not be surprised if one were carried out.
US intelligence officials say satellite images have shown increased activity at a suspected North Korean test site, according to US media reports.
Both US and South Korean officials have warned of "grave consequences" should a second test go ahead.
Mr Tang, who went to North Korea on Thursday with a special message from China's President Hu Jintao, told Ms Rice: "Fortunately my visit this time has not been in vain".
He did not elaborate, publicly, on the goals of his visit.
But China's foreign minister, Li Zhaoxing, later said Mr Tang had spoken to the North Korean leader about how to kick-start six-nation talks on resolving North Korea's nuclear ambitions which have been stalled since late 2005.
NEW UN SANCTIONS
Bans sale to, or export from, N Korea of military hardware
Bans sale or export of nuclear and missile related items
Bans sale of luxury goods
Freezes finances and bans travel of anyone involved in nuclear, missile programmes
Allows inspection of cargo to and from N Korea
Stresses new resolution needed for further action
"At least it increased mutual understanding. Everyone discussed how to restart progress in the six-party talks as quickly as possible," Mr Li said.
North Korea has stated that it wants US financial and other sanctions lifted before it will consider resuming the talks, which have stalled for over a year. Some analysts say North Korea's nuclear test made the talks meaningless.
China, North Korea's closest ally and main trade partner, is thought to have most influence over the communist state.
It backed a resolution in the UN Security Council that imposed sanctions targeting Pyongyang's missile and weapons programmes.
But Beijing has baulked at one clause allowing inspections of cargo going to and from North Korea for banned items, fearing it will raise tensions further.