The release of Laura Ling and Euna Lee was a sign of North Korea's "humanitarian and peaceloving policy," the Korean Central News Agency reported.
North Korean officials had told relatives of the women that they would release the reporters to Clinton, a Washington source told Politico. The paper reported that the White House approved Clinton's mission, which has been planned for weeks.
Clinton and Kim met in Pyongyang and Clinton passed along a verbal message from President Barack Obama, news agencies reported. Details of their discussion have not been released, but the two exchanged "a broad range of opinion," the Agence France-Presse reported.
Washington has asked for amnesty for the two women who were working as reporters for Clinton's former Vice President Al Gore and his Current TV media venture. They were captured at the Chinese-North Korean border in March and sentenced in June to 12 years of hard labor.
Ling and Lee were making a documentary about North Korean refugees when they were detained.
Upon arrival in North Korea, Clinton was greeted at the airport by Vice Foreign Minister Kim Kye Gwan and the deputy speaker of parliament, and was presented flowers by a young girl.
Republican Sen. Lindsey Graham of South Carolina told NBC's Today Show it was not clear whether Clinton would be discussing policy issues.
"It would be nice if it's the foundation for a better relationship," Graham said, reported Reuters.
"If he could sit down with the North Koreans and convey a message from the administration and the Congress to be more reasonable when it comes to verifying their nuclear program and getting away from the development of nuclear weapons, it'd be a good thing."
B.R. Myers, an expert on the North's state ideology at the South's Dongseo University told Reuters that Clinton's visit allows the North to show its residents, who face deepening poverty, that the nuclear weapons program is making the outside world take it more seriously and the visit will be certain to be portrayed as tribute by the United States.
And it will confirm to North Korea that bad behavior will be rewarded further, Myers said. "It sends all the wrong signals."
A senior official travelling with U.S. Secretary of State Hillary Clinton, who has been critical of North Korea in recent weeks, told Reuters there would be no comment during the mission.
"Our interest here is the successful completion of the mission and the safe return of the journalists," the source said.
The meeting with Kim would be the North Korean leader's first with a prominent Western figure since he reportedly suffered a stroke a year ago. It is the second time a former U.S. president has headed to the North to try to defuse a crisis. Former President Jimmy Carter flew there in 1994 when tensions were running high, again over the North's nuclear weapons program.
The White House would not comment until the mission was complete.
"While this solely private mission to secure the release of two Americans is on the ground, we will have no comment," White House spokesman Robert Gibbs said in a statement. "We do not want to jeopardize the success of former President Clinton's mission."
Many analysts predicted Pyongyang would use the journalists as leverage to wring concessions from Washington, which led pressure for U.N. sanctions on the North for a May nuclear test.
Yun Duk-min of the Institute of Foreign Affairs and National Security in Seoul told Reuters the visit held out the possibility of "a dramatic turnaround by North Korea that could lead to a new phase of negotiations."
But trade data suggest the North may be resorting more to barter trade to make it more difficult for the international community to pressure Pyongyang through sanctions.
---- Compiled from wire reports and other media sources