"This will be a long and difficult transition, but I have confidence that you will succeed in realizing the dream of a representative government," Panetta said during a news conference with Prime Minister Abdurrahim el-Keib.
"The torch of freedom that has passed throughout the centuries and now passes from nation to nation in the Middle East and North Africa burns brightly here in Libya. May it light your way to a future of peace, prosperity and freedom," Panetta said.
While his visit was brief, Panetta made history as the first U.S. Pentagon chief to set foot on Libyan soil.
He evoked U.S. history, too, with a visit to the cemetery presumed to hold remains of U.S. sailors killed in Tripoli harbor in 1804. Their deaths were memorialized in the famous "shores of Tripoli" line in the Marine Corps hymn.
Both Panetta and al-Keib expressed confidence that the fledgling government will be able to reach out to the militias and bring them together.
"We know how serious this issue is," said al-Keib, "We realize it is not matter of saying 'OK, put down your arms, go back to work or do what you want to do.' We realize that there are lots of things that we need to be organized."
More broadly, Panetta said the revolts across the region represent a quest for sovereignty by the people, but they will all involve different approaches and challenges.
During meetings with the Libyan leaders, Panetta expressed concern about al-Qaida in the Islamic Maghreb militants gaining a foothold amid the chaos of an unfolding democracy. But they told him that the Libyan people will reject the terrorist group, said a senior defense official, who spoke on condition of anonymity because the discussions were private.
Panetta's motorcade from the airport into the city provided views of the nation's violent past and future promise - lush orange groves, carcasses of bombed buildings and charred and graffiti-covered compound once occupied by Gadhafi. Flying from rooftops were the green, black and red flags, adorned with a star and a crescent, belonging to the new government.
At one point, amid the graffiti splashed across the walls of Gadhafi's former compound was a short comment in English: "Thanx US/UK."
The visit also put the man who has led much of the U.S. terrorism fight over the past several years at the scene of one of the first American wars on terror, more than two centuries ago.
Panetta went to what historians believe is the gravesite of as many as 13 U.S. sailors killed in 1804, when the Navy ship Intrepid exploded while slipping into Tripoli harbor to attack pirate ships that had captured an American frigate.
As the story goes, governments along the Barbary coast had turned to state-sponsored piracy to raise money, attacking and taking over merchant ships, enslaving their crews and stealing their bounties. Unwilling to pay fees to protect its ships, the U.S. sent the Navy frigate Philadelphia to the region but it ran aground just off Tripoli and was captured.
President Thomas Jefferson sent a team to get the Philadelphia back or destroy it. Under cover of darkness, the Intrepid sailed into the harbor, killed about 25 pirates and burned the Philadelphia.
A few months later, Jefferson sent the Intrepid back to destroy as many of the pirate ships as possible. The plan was to pack the ketch with explosives, sail into the harbor and blow her up.
The 13 sailors never got to their destination. The ship exploded prematurely killing all aboard and the next day bodies washed ashore. They were buried outside Tripoli, but in 1949 the remains were moved to The Protestant Cemetery by the Libyan government.
On Saturday, Panetta walked into the small walled cemetery and slowly made his way to a corner where five large but simple white gravestones mark the graves of the American sailors. Markers on four of the stones read, "Here lies an American sailor who gave his life in the explosion of the United States Ship Intrepid in Tripoli Harbour, Sept. 4, 1804."
Panetta placed a wreath at the site and, after a moment of silence, placed one of his U.S. secretary of defense souvenir coins on top of one of the stones.
New life was breathed into the long-ago tale by Congress this year. Lawmakers, prodded by descendants of the sailors, added provisions to the defense bill ordering the Pentagon to study the feasibility of exhuming the bodies and bringing them home to America.
In a statement, Panetta said the recent effort to restore the cemetery is "a symbol of the values we share."
Officials said that Panetta made no specific offers of assistance to the Libyan leaders, and he told reporters that there was no discussion of providing military equipment or weapons.
"They have to determine what their needs are and what kind of assistance is required," he said. "And whatever they need, the United States will be happy to respond."
Ahead of Panetta's visit, the Obama administration announced it had lifted penalties that were imposed on Libya in February to choke off Gadhafi's financial resources while his government was using violence to suppress peaceful protests.
The U.S. at the time blocked some $37 billion in Libyan assets, and a White House statement said Friday's action "unfreezes all government and central bank funds within U.S. jurisdiction, with limited exceptions."