His mission accomplished, former President Bill Clinton left Pyongyang early Wednesday accompanied by American journalists Euna Lee and Laura Ling after North Korean leader Kim Jong Il pardoned the women from their 12-year prison sentences. Clinton and the two Californians were heading back to the US, his spokesman Matt McKenna said, less than 24 hours after the former US leader landed in the North Korean capital on a private, humanitarian trip to secure their release. The women, dressed in short-sleeved shirts and jeans, appeared healthy as they climbed the steps to the plane and shook hands with Clinton before getting into the jet, APTN footage in Pyongyang showed. McKenna said the flight was bound for Los Angeles, where the journalists will be reunited with their families. The White House had no comment. Their departure was a jubilant conclusion to a more than four-month ordeal for the women arrested near the North Korean-Chinese border in March and sentenced in June to 12 years of hard labor for illegal entry and engaging in "hostile acts." Clinton's landmark trip to Pyongyang also resulted in rare talks with reclusive Kim Jong Il that state-run media described as "wide-ranging" and "exhaustive." The meeting was Kim's first with a prominent Western figure since reportedly suffering a stroke nearly a year ago. North Korean media characterized the women's release as proof of "humanitarian and peace-loving policy." State media said Clinton apologized on behalf of the women and relayed President Barack Obama's gratitude. The report said the visit would "contribute to deepening the understanding" between North Korea and the United States. While the White House emphasized the private nature of Clinton's trip, his landmark visit to Pyongyang to free the Americans was a coup that came at a time of heightened tensions over North Korea's nuclear program. The meeting also appeared aimed at dispelling persistent questions about the health of the authoritarian North Korean leader, who was said to be suffering from chronic diabetes and heart disease before the reported stroke. Kim smiled broadly for a photo standing next to a towering Clinton. He was markedly thinner than a year ago, with his graying hair cropped short. The once-pudgy 67-year-old, who for decades had a noticeable pot belly, wore a khaki jumpsuit and appeared frail and diminutive in a group shot seated next to a robust Clinton. North Korea accused Ling, 32, and Lee, 36, both of former Vice President Al Gore's Current TV media venture, of sneaking into the country illegally. US Secretary of State Hillary Rodham Clinton urged North Korea last month to grant them amnesty, saying they were remorseful and their families were anguished by their detention. The journalists' release followed weeks of quiet negotiations between the State Department and the North Korean mission to the United Nations, said Daniel Sneider, associate director of research at Stanford University's Shorenstein Asia-Pacific Research Center. Clinton "didn't go to negotiate this, he went to reap the fruits of the negotiation," Sneider said. Pardoning Ling and Lee and having Clinton serving as their emissary served both North Korea's need to continue maintaining that the two women had committed a crime and the Obama administration's desire not to expend diplomatic capital winning their freedom, Sneider said. "Nobody wanted this to be a distraction from the more substantially difficult issues we have with North Korea," he said. "There was a desire by the administration to resolve this quietly and from the very beginning they didn't allow it to become a huge public issue." The families of Ling and Lee said they were "overjoyed" by the pardon. "We are so grateful to our government: President Obama, Secretary Clinton and the US State Department for their dedication to and hard work on behalf of American citizens," the families said in a statement. "We especially want to thank President Bill Clinton for taking on such an arduous mission and Vice President Al Gore for his tireless efforts to bring Laura and Euna home. "We are counting the seconds to hold Laura and Euna in our arms," the statement said. Lee, a South Korean-born US citizen, is the mother of a 4-year-old. Ling, a California native, is the younger sister of Lisa Ling, a correspondent for CNN as well as "The Oprah Winfrey Show" and "National Geographic Explorer." They were arrested as they reported about the trafficking of women. It's unclear if they strayed into the North or were grabbed by aggressive border guards who crossed into China but recent statements suggested they admitted to deliberately crossing into the country. The Committee to Protect Journalists also welcomed their release. North Korean state media said Clinton and Kim held wide-ranging talks, adding that Clinton "courteously" conveyed a verbal message from Obama. In Washington, White House spokesman Robert Gibbs denied Clinton went with a message from Obama. "That's not true," he told reporters. "While this solely private mission to secure the release of two Americans is on the ground, we will have no comment" until the mission is complete, Gibbs said in a statement. "We do not want to jeopardize the success of former President Clinton's mission." Clinton was accompanied by John Podesta, his one-time White House chief of staff, who also is an informal adviser to Obama. Clinton was accorded honors typically reserved for heads of state. Senior officials, led by Vice Foreign Minister Kim Kye Gwan, who also serves as the regime's chief nuclear negotiator, met his private unmarked plane as it arrived Tuesday morning. Video from the APTN television news agency showed Clinton exchanging warm handshakes with officials and accepting a bouquet of flowers from a schoolgirl. Kim later hosted a banquet for Clinton at the state guesthouse, Radio Pyongyang and the Korean Central Broadcasting Station reported. The VIPs and Kim posed for a group shot in front of the same garish mural depicting a stormy seaside landscape that Clinton's secretary of state, Madeleine Albright, posed for during her historic visit to Pyongyang in 2000. But not long ago, North Korea's Foreign Ministry had harsh words for his wife, describing her as "a funny lady" who sometimes "looks like a primary schoolgirl and sometimes a pensioner going shopping." In the past, envoys have been dispatched to Pyongyang to secure the release of Americans. In the 1990s, New Mexico Gov. Bill Richardson, a congressman at the time, went twice on similar missions: in 1994 to arrange the freedom of a US pilot whose helicopter strayed into North Korean airspace and again two years later to fetch an American detained for three months on spying charges. Richardson, Clinton and Gore, Clinton's vice president, had all been named as possible envoys to bring back Lee and Ling. However, the decision to send Clinton was kept quiet, revealed only when he turned up Tuesday in Pyongyang. The trip was reminiscent of one 15 years ago by former President Jimmy Carter when Clinton was in office, also at a time of tensions over North Korea's nuclear program. Carter's visit - he met with Kim Jong Il's father, the late Kim Il Sung - helped thaw the deep freeze in relations with the Korean War foe and paved the way for discussions on nuclear disarmament. Clinton later sent Albright to Pyongyang for talks with Kim in a high point in the often rocky relations with North Korea. Discussions about normalizing ties went dead when George W. Bush took office in 2001 with a hard-line policy on Pyongyang. The Obama administration has expressed a willingness to hold bilateral talks - but only within the framework of the six-nation disarmament talks in place since 2003. North Korea announced earlier this year it was abandoning the talks involving the two Koreas, Japan, Russia, China and the US The regime also launched a long-range rocket, conducted a nuclear test, test-fired a barrage of ballistic missiles and restarted its atomic program in defiance of international criticism and the UN Security Council. Last month, the US Navy tailed a North Korean cargo ship as it sailed south suspected of carrying cargo banned under a UN resolution on board until the vessel turned around and returned to port. Kim inherited leadership of impoverished North Korea upon his father's death in 1994, 20 years after being anointed the heir apparent. Kim has not publicly named his successor but is believed to be grooming his third son, 26-year-old Jong Un, to take over.