SEOUL, South Korea – North Korea welcomed former President Bill Clinton to Pyongyang with flowers and hearty handshakes Tuesday as he arrived in the communist nation on a surprise mission to bring home two jailed American journalists.

Clinton landed in the North Korean capital in an unmarked jet. On arrival he shook hands with Vice Foreign Minister Kim Kye Kwan and the deputy speaker of parliament. Footage from the television news agency APTN showed Clinton bowing and smiling as a young girl presented him with flowers.

The unusually warm exchange between officials from communist North Korea and the ex-leader of a wartime foe comes amid heightened tensions between Washington and Pyongyang over the regime's nuclear program. In recent months, North Korea has abandoned a disarmament pact, launched a long-range rocket, conducted a nuclear test and test-fired a barrage of ballistic missiles in defiance of the U.N. Security Council.

Clinton was making his first trip to North Korea in hopes of securing the release of Laura Ling and Euna Lee, reporters for former Vice President Al Gore's California-based Current TV media venture who were arrested along the North Korean-Chinese border in March.

But the visit could reap rewards beyond the women's release, with Clinton and North Korean officials broaching the nuclear impasse, diplomatic relations and other long-standing issues between Washington and Pyongyang, analysts said. Kim, the vice foreign minister, also serves as North Korea's chief nuclear negotiator.

"This is a very potentially rewarding trip. Not only is it likely to resolve the case of the two American journalists detained in North Korea for many months, but it could be a very significant opening and breaking this downward cycle of tension and recrimination between the U.S. and North Korea," Mike Chinoy, author of "Meltdown: The Inside Story of the North Korean Nuclear Crisis," said in Beijing.

North Korea accused Ling, 32, and Lee, 36, of sneaking into the country illegally in March and engaging in "hostile acts," and the nation's top court sentenced them in June to 12 years of hard labor. The U.S. and North Korea do not have diplomatic relations, but officials were believed to be working behind the scenes to negotiate their release.

Clinton's administration had relatively good relations with Pyongyang, and both he and Gore, his vice president, had been named as possible envoys to bring back Lee and Ling. Also mentioned was New Mexico Gov. Bill Richardson, who in the 1990s traveled twice to North Korea to secure the freedom of detained Americans.

However, the decision to send Clinton, whose wife is now secretary of state, was kept quiet.

A senior U.S. official confirmed to reporters traveling to Africa with U.S. Secretary of State Hillary Rodham Clinton that the former president was in North Korea to secure the journalists' release, but said 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."

North Korea's official Korean Central News Agency announced Clinton's visit with a brief dispatch but did not say who he would be meeting during his trip.

There was speculation Clinton might see leader Kim Jong Il, who analysts say is eager to smooth over relations with Washington as he prepares to name a successor.

Kim, 67, reportedly is in ill health, suffering a stroke a year ago on top of chronic diabetes and heart disease. He rules the impoverished communist nation of 24 million with absolute authority, but has not publicly named the next leader. He is believed, however, to be grooming his third son, 26-year-old Jong Un, to take over.

Internal stability is key to a smooth transition, and establishing relations with Washington would be one way to rule out a threat from a superpower that has 28,500 troops stationed just on the other side of the border with South Korea, analysts said. The two Koreas remain technically at war because their three-year conflict ended in a truce, not a peace treaty, in 1953.

Releasing the journalists would be a face-saving segue into talks, analysts said.

"When you're dealing with Kim Jong Il in North Korea, his word has been, may still be, law. And so it is actually possible to sit down and have a significant conversation that could change the current trajectory of U.S.-North Korean relations," said Jim Walsh, a nuclear proliferation expert at the Massachusetts Institute of Technology.

During a nuclear standoff with North Korean in 1994, former President Jimmy Carter went to Pyongyang and met with leader Kim Il Sung, Kim Jong Il's late father. That visit, during Clinton's presidency, led to a breakthrough accord months later.

The last high-ranking U.S. official to meet with Kim Jong Il was Madeleine Albright, Clinton's secretary of state, who visited Pyongyang in 2000 at a time of warming relations. Ties turned frosty when George W. Bush took office in 2001.

Since President Barack Obama took office, Pyongyang has expressed interest in one-on-one negotiations with Washington. The latest provocations were seen in part as a way to draw a concerned U.S. into bilateral talks.

Washington says it is willing to hold such talks with the North, but only within the framework of international disarmament negotiations in place since 2003. Those talks involve China, Japan, the two Koreas, Russia and the United States. North Korea has said it will never return to the six-nation disarmament process.

Lee and Ling were captured in North Korea's far northeast in the midst of the nuclear standoff. They had traveled to the border region in China to report on women and children defectors from North Korea.

Their families and U.S. officials have pushed for their release, noting that Ling has a medical condition and that Lee has a 4-year-old daughter.

Hillary Rodham Clinton has urged North Korea to grant them amnesty, saying the women were remorseful and their families anguished.

"We are still very distressed by the absence of Laura and Euna but remain hopeful that a positive resolution can be reached," TV journalist Lisa Ling, Ling's older sister, told the Committee to Protect Journalists in July.

___