Both new leaders have vowed to shelve urban development projects, judging them unnecessary and too expensive at a time when one in four workers is out of a job in Spain. Tens of thousands of new homes also remain unsold following the collapse of a property bubble in 2008.
Ada Colau, a 41-year-old anti-eviction activist, was sworn in as mayor of Barcelona on Saturday while Manuela Carmena, a 71-year-old retired judge, took the reins at Madrid city hall, after nationwide local elections last month in which the ruling conservative Popular Party took a drubbing.
Shares in Spanish builders have slumped since the May 24th election, reflecting concerns by investors.
Spanish infrastructure group OHL has lost a third of its value, builder FCC is down by nearly 17 percent while its rival ACS has lost just over nine percent.
Madrid had the greatest number of real estate projects awaiting approval before the local elections, which put an end to over two decades of Popular Party rule in the Spanish capital of three million residents.
The largest is an ambitious public-private partnership dubbed "Operation Chamartin" named for the district in northern Madrid where investors want to create a new financial centre.
It calls for the construction of several skyscrapers, three new metro stations and around 17,000 new homes.
The project's backers say it would create 121,000 badly needed jobs for an investment of €6 billion ($6.7 billion).
But Carmena, whose race for mayor was backed by Spain's new anti-austerity party Podemos, has said she opposes the project in its current form.
"The north of the city does not need 17,000 new homes," she told top-selling daily newspaper El Pais.
Carmena said she wants to "curb speculative real estate projects which are under way" following a lengthy building boom whose collapse in 2008 sent the Spanish economy into a tailspin.
New hotel moratorium
On Spain's northeast Mediterranean coast, Barcelona's new mayor has vowed to place a moratorium on approving the construction of new hotels as part of a plan to ensure the city does not "end up like Venice".
She has also said she will stop the construction of a large supermarket and block the expansion of two others to help preserve small shops.
The new mayors cannot outright cancel projects which have already been approved, said real estate consultant Jose Luis Bartome.
"They will be terminated, but through delays and changes," he said.
He considers "Operation Chamartin" a project that would meet the need for housing and urban renewal in Madrid.
Spain's second-largest bank BBVA, one of the project's creditors, said it "will work with public administrations to satisfy the needs of residents".
Spanish construction group Acciona, which is in the race to build another Madrid mega-project - a new complex of court buildings estimated to cost €1.2 billion - is also cautious about the new view from city hall regarding big projects.
"We must wait and see what they say," a company spokeswoman said.
Audience with king
A Madrid architect, who spoke under the condition that he not be named, said the election outcome had already cost him a project to build 40 homes on an empty plot.
"The Friday (before the municipal elections) it was almost sold. The Monday (after the vote), the French investors backed away," he said.
There is "uncertainty" over how the municipality will manage building permits, he added.
Chinese billionaire Wang Jianlin, who earlier this year bought a stake in Spanish football club Atletico Madrid after last year snapping up a landmark Madrid skyscraper which has stood empty for years, is reportedly worried.
He has demanded an audience with King Felipe VI, according to a report in online news site El Confidencial, which was not confirmed by the royal palace.
Wang wants to buy two million square metres of land in Madrid to build 11,000 houses, stores and a theme park, but locals are lobbying city officials to turn the site into a hospital.
By Laure Fillon