Tony Blair says Libya's Muammar Gaddafi is willing to join Britain in the fight against terrorism.
The pair met in a Bedouin tent outside Tripoli
After shaking hands with Colonel Gaddafi at the start of the historic talks, the prime minister said there was real hope for a "new relationship".
People should not forget the past, they should move beyond it, Mr Blair said.
Thursday's Tripoli meeting follows Libya's renunciation of weapons of mass destruction in December. Mr Blair said such changes were "extraordinary".
After the talks took place Mr Blair headed to an EU summit in Brussels set to be dominated by the issue of security in the wake of the Madrid terror attack.
As Mr Blair met Mr Gaddafi, it was announced Anglo-Dutch oil giant Shell had signed a deal worth up to £550m for gas exploration rights off the Libyan coast.
It was also announced that British police officers would travel to Libya on 3 April to continue investigations into the murder of Pc Yvonne Fletcher.
The police officer is thought to have been shot dead by a gunman inside the Libyan embassy as she helped police a demonstration outside it in 1984.
Mr Blair 's Tripoli visit has been criticised by some politicians and received a mixed response from relatives of the victims of the Lockerbie bombing.
Asked if he had felt queasy about meeting Colonel Gaddafi, Mr Blair said: "It was strange given the history to come here and do this and of course I am conscious of the pain that people have suffered as a result of terrorist actions in the past.
"But the world is changing and we have got to do everything we possibly can to tackle the security threat that faces us."
That meant pursuing terror groups but also offering partnership to states renouncing terrorism and weapons of mass destruction.
Mr Blair said he had been struck by how Colonel Gaddafi wanted to make "common cause with us against al-Qaeda, extremists and terrorism".
He insisted he was aware of potential pitfalls.
"Trust on both
sides will take time to establish," he argued.
"But the signs are better than they have been for many years. And the future prize in terms of security not just of this region but the
wider world - indeed our own country - is great."
Earlier, Mr Blair greeted the Libyan leader in a Bedouin tent on the outskirts of Tripoli, saying: "It's good to be here at last
after so many months."
Colonel Gaddafi spoke first in Arabic before switching to English to tell the prime minister: "You did a lot of fighting on
this issue and seem exhausted."
Mr Blair replied: "There's been a lot to do."
The Libyan leader added: "You look good, you are still
It is the first visit by a British prime minister since 1943 and comes after US Assistant Secretary of State William Burns this week became the most senior American to visit since the 1969 coup which brought Colonel Gaddafi to power.
BBC News political editor Andrew Marr said: "This is an absolutely pivotal moment in the history of the region, possibly even in the history of the war against terrorism."
In addition to Shell, other British firms have already begun tapping the opportunities in Libya.
Among them is defence contractor BAE Systems, which says it is in talks over aviation projects.
UK-LIBYA KEY DATES
World War II: Winston Churchill visits Libya
1984: Wpc Fletcher shot outside Libyan Embassy
1988: Lockerbie bombing kills 270 people
April 1999: Libya hands over Lockerbie suspects to UN
July 1999: Britain restores diplomatic relations after Libya accepts "general responsibility" for Wpc Fletcher murder
2002: Foreign Office Minister Mike O'Brien meets Gaddafi in first visit by British minister since 1969 coup
August 2003: Libya accepts responsibility for Lockerbie and agrees to pay compensation
December 2003: Gaddafi renounces weapons of mass destruction programmes
February 2004: Libyan foreign minister visits London, plans for Tony Blair's visit announced
Tony Blair's visit to Libya has divided families of those killed at Lockerbie.
American Kathleen Flynn, whose son John Patrick died, said she found the trip was "insulting".
But Jim Swire, of the UK Families Flight 103 campaign group, said the visit would "greatly diminish the
chances of a backsliding of support for terrorism".
UK opposition leader Michael Howard said it was very odd timing for Mr Blair to visit Libya straight from a memorial service for those killed by terrorists in Madrid.
Mr Howard said he did not oppose contact with Libya but thought it should have been at a less senior level.
Liberal Democrat foreign affairs spokesman Sir Menzies Campbell said the potential prize of helping Libya "in from the cold" made Mr Blair's risk worth taking.