Britain denied the joint position was a climb-down after it had repeatedly called for him to quit the country, while France last week was the first to openly suggest he could stay under a negotiated settlement.
Analysts and diplomats said the joint stance at a meeting of their foreign ministers Monday showed rising pressure to get Qaddafi out of power and end their military operations which are dragging on longer than expected.
"There is pressure from the French side to try to find a political solution," said Denis Bauchard, of the Paris-based international relations institute IFRI.
"The British are going the same way as France, who are taking the lead in this matter."
There was little sign that Qaddafi's departure was imminent, however, some four months after Western powers launched their air campaign to stop his forces crushing a rebellion.
Top US officer Admiral Michael Mullen spoke recently of "stalemate" in NATO's campaign, launched in March against Qaddafi's forces in accordance with a UN Security Council resolution, and spearheaded by France and Britain.
French officials warn that a settlement will be fraught with complications, since Qaddafi would have to be protected from assassination and may demand protection from prosecution as part of a negotiated deal.
"The only possible way out for Qaddafi is feet first," dead, said one French diplomat who asked not to be named.
A British diplomatic source denied any change to its strategy on Libya after Foreign Secretary William Hague suggested Qaddafi could be allowed to stay in the country if he quit power, having repeatedly called for him to leave.
The International Criminal Court has issued an arrest warrant for Qaddafi on charges of crimes against humanity during his crackdown on the rebellion that began in mid-February. He "should face justice," the British source said.
"Obviously him leaving Libya itself would be the best way of showing the Libyan people that they no longer have to live in fear of Qaddafi," Hague said Monday ahead of talks with French counterpart Alain Juppé.
"But as I have said all along, this is ultimately a question for Libyans to determine," added Hague. "Whatever happens, Qaddafi must leave power."
Juppé said the allies were in "perfect co-operation" over the UN-sanctioned mission, which began in March, despite suggestions in France that the mission was dragging on too long.
"We think that we must continue to exert strong pressure on the Libyan regime with the same methods," he said.
The leader of the Libyan rebels' Transitional National Council, Mustapha Abdel Jalil, appeared to soften his stance, saying in Monday's Wall Street Journal that "Qaddafi can stay in Libya but it will have conditions."
He said these terms would be decided by the rebels, who are battling against forces loyal to Qaddafi, trying to dislodge him.
"One of the possibilities being considered is that he stay in Libya but on the clear condition that he steps aside from Libyan political life," Juppé said last week.
"That is what we are waiting for before we start the political process for a ceasefire."