Three days later, voters spurned the Popular Party and handed victory to the Socialists. Their leader, Jose Luis Rodriguez Zapatero, quickly reiterated a pre-election promise to bring Spanish troops home from Iraq.
"If there is no change and the United Nations takes over the situation [in Iraq] and the occupiers relinquish political control, the Spanish troops will come back, and the deadline for the withdrawal will be 30 June," Zapatero said.
All that has led some observers to reach a disheartening conclusion -- that terrorists can use bombs to achieve their political aims and even sway a democratic election.
"This is a devious network which is clearly trying to achieve political and strategic impact," said Paul Wilkinson, the head of the Centre for the Study of Terrorism and Political Violence in St. Andrews, Scotland.
"I'm not sure they could have been clever enough politically to know exactly how the government would react. But they would certainly be able to gauge that the public would be worried about the possibility of future attacks if the Spanish government didn't change its policy. So the effort was to bring about a change of policy towards [Iraq]. And in that, you must concede that they did indeed bring about that change," Wilkinson said.
Wilkinson notes it's not the first time terrorist attacks have achieved their desired impact. Palestinian suicide bombings in Israel in the mid-1990s severely undermined the Oslo peace accord, he says. And a 1983 suicide attack on U.S. Marines in Lebanon contributed to the withdrawal of the multinational peacekeeping force there.
"We should not fall into the trap of believing that terrorism is unable to achieve a major impact,” he says. “These terrorists study ways of achieving maximum damage and disruption -- of course, including economic disruption -- and we should take the threat seriously. Governments are clearly aware that this indicates that Al-Qaeda is very much in business, and therefore we need to maximize cooperation against it."
To be sure, it's not yet 100 percent certain that Al-Qaeda or other Islamist groups were behind the attacks.
And the pessimistic view that the elections represent a victory for terrorists is not the only theory out there.
A positive spin says that this was democracy at work -- voters got rid of the party whose support for the Iraq war was deeply unpopular with about 90 percent of the population. Still, polls had put the Popular Party in the lead in the immediate run-up to the election.
Another analysis says it wasn't so much payback for Iraq, but rather public anger at the government's initial insistence the attack was the work of the Basque separatist group ETA and its unwillingness to contemplate that Islamic militants may have been responsible. Some perceive this to have been an effort by the Popular Party to contain any possible political damage from its unpopular stance on Iraq in the days before the election.
Still, even the very idea terrorists may have influenced the election has prompted fears it could embolden them for further strikes -- and even raises the possibility the strategy may be repeated elsewhere.
The United States has a presidential election in November. Elections are also coming up in Britain.
Helen Wallace is an expert on European politics at the European University Institute in Florence.
"I think in many European countries, including the UK, we are accustomed to terrorist incidents of various kinds. We have long experience in the UK of both Irish terrorism and Middle Eastern terrorism. I'm currently living in Italy, where there have been terrorist incidents, politicians murdered. So this isn't a new phenomenon for us. But obviously what happened in Madrid was on a scale that none of us is familiar with, a horrifying scale, and people are bound to be very nervous about it. In the UK the level of security alerts has been very high ever since the attacks on the Twin Towers in New York and everyone will redouble their efforts now to try and protect against a very difficult enemy," Wallace said.
Of course, worries are not restricted to election times.
Zbigniew Siemiatkowski, the head of the Polish Intelligence Agency, said Poland could be a target of terrorist attacks because it has troops in Iraq.
And it's not just those who supported the Iraq war or who have troops here who should be worried.
Wilkinson says other Western countries are at risk, too, since groups like Al-Qaeda are opposed to many of the policies of Western democracies, particularly those on the Middle East.