Here is the full text of the speech Tony Blair delivered after talks with Portuguese Prime Minister Jose Manuel Durao Barraso.
I thank Jose Manuel for hosting me here today.
I thank the Portuguese Government and people for the support the GNR are giving British forces in the South of Iraq.
I know from my own visit how deeply it is appreciated by the people there.
Mr Blair held talks with his Portuguese counterpart
Earlier today I attended a moving commemoration of the lives of those who died in Madrid on 11 March.
There was a sense of sadness but also of dignity and of unity which affected us all deeply.
Let me repeat again my profound condolences to the Spanish people over their loss.
The grief, felt and shared round the whole of Europe and the world, at this atrocity has been intense.
Everyone everywhere condemns without reservation the act of terrorism.
However, outside of the shared grief, has been another debate.
Some, like myself, believe that the war in Iraq is all part of the same global threat to our security which we face.
Others believe, with equal passion that the war was an unjustified provocation of the Muslim world or at least a diversion from the true war against terrorism.
This is a disagreement we cannot at present resolve.
Perhaps we never can but my plea tonight, here in Portugal, whose prime minister with great courage supported our action in Iraq but whose people like the British people were sorely divided over it, is that for now we surmount this division and seek common ground.
It would indeed be a ghastly victory for the evil people who committed the carnage of the innocent in Madrid, if in addition to the destruction and death they also caused us to turn in recrimination on each other.
At my meeting with Mr Zapatero, the prime minister elect of Spain this morning, both of us agreed that unity and solidarity in the face of terrorism was the only possible response.
In any event, for al-Qaeda to pretend that the war in Iraq is the reason for their campaign of violence is a cruel deceit.
There was no occupation of Iraq when Embassies were attacked in Nairobi and Dar-es-Salaam killing over 300 people in 1998 or when the USS Cole was hit and sailors killed by a suicide bomb back in the year 2000.
Morocco and Saudi Arabia took no part in the war but have seen scores of innocent people blown to pieces.
Turkey did not take part in the war in Iraq but many more Turks than foreigners were killed in the suicide attacks in November. Indonesia suffered Bali before the Iraq war even began.
German and French citizens died in bombs in Tunisia and Pakistan.
September 11th was not in retaliation for an attack by the US on al-Qaeda. But an entirely unprovoked attack by al-Qaeda on the US.
Of course they demand we withdraw from Iraq. But their demands do not stop there.
They also demand we withdraw from Afghanistan.
They demand we withdraw from all places in the Middle East, even when there with the consent of the country.
They demand the elimination of Israel.
They even have demanded the reintroduction of a caliphate on the Iberian Peninsula.
And they demand in any Muslim country anywhere, a Taliban state, where human rights are curtailed, freedom reduced to religious slavery, women sent back to the dark ages.
Recall the words they used just a few weeks ago in a statement celebrating their terrorism: "You love life, we love death".
I came to Spain yesterday from Northern Ireland, where we have worked so hard, for so long, to bring a durable peace in place of terrorism.
I believe in trying to negotiate where negotiation can achieve peace on honourable terms.
But al-Qaeda and the religious fanaticism that unites them and similar groups, have no demands we can negotiate upon, honourably or otherwise.
We either defeat them or live under their shadow of fear.
In truth there is no hiding place from these terrorists, no exemption from their evil.
So let us put aside, for this purpose at least, a disagreement over the war in Iraq and unify to defeat terrorism around an agenda that is just and humane, as their agenda is unjust and inhumane.
First, let us pledge ourselves at tomorrow's European Summit, individually as nations and collectively as the EU, to do all we can to detect, root out and defeat the terrorists on our soil.
Let us co-operate on security, work together to prosecute terrorist crime, share information, show total solidarity in our determination against terrorism.
Second, let us accept, whatever our differences over the war, it is in all our interests and in the interests of the peaceful majority in the Muslim world that Iraq be helped to be a sovereign, independent, stable, democratic state, where there is religious tolerance, human rights and equality for all.
The terrorist, many with links to al-Qaeda, are in Iraq now killing innocent Iraqis.
Our job is to defeat them and help Iraq on its feet.
If we succeed in this task, it is a huge blow to the lies of al-Qaeda. If they succeed in stopping us, they will be hugely emboldened.
Third, let us acknowledge that Afghanistan, where by and large few divisions over military action exist, is also our obligation and responsibility.
Let us ensure at the forthcoming conference in Berlin that we commit the help necessary for that country, for so long in the grip of terror, to continue its progress and reach the goal the vast majority of Afghans want.
Fourth, let us offer to states that want to renounce terrorism and the development of WMD, our hand in partnership to achieve it, as Libya has rightly and courageously decided to do.
That does not mean forgetting the pain of the past. But it does mean recognising change when it happens.
Fifth, even after the sad events of the past few days, it is our duty to work, in Europe and with the US and UN to bring renewed impetus to the MEPP.
Nothing could better demonstrate the lies of the extremists' propaganda than a just settlement of the Palestinian issue based on a viable two State solution.
Sixth, let us show by our willingness to bring Turkey, a proud Muslim nation into the EU on the same and equal terms as all others, that Europe is committed not just in word but in deed to a Europe of diverse races, cultures and religions all bound together by common rules and a sense of human solidarity and mutual respect.
This much surely can be our common ground.
It can show our dedication to defeating terrorism not only by pursuing terrorists but by remedying injustice, showing by our actions that we are also dedicated to eliminating the causes upon which the terrorists prey; doing all we can to prevent a new generation of terrorists arising, based on this perversion of the true and peaceful faith of Islam.
At this time, with the tears and tragedy of Madrid in our minds, let us unite, put aside our differences, refuse to be divided by terrorism and express our strength and confidence in our own way of life which we will defend to the end.