A crowd estimated by police at 3,000-5,000 converged at a main gate to the palace compound, and hung a banner on it saying "Christophias is a murderer and must go to jail."
They had marched in response to calls on networking sites and mobile texts to demonstrate against what is widely perceived as government negligence in not preventing the Mediterranean island's worst peacetime military accident.
News that makes sense
Your trusted source for staying up-to-date with the world around you. Get free daily news updates and analysis, straight to your inbox.
FIRE RAVAGES BASE
Around dawn on Monday, as a fire ravaged a naval base on the south coast, a seized Iranian arms cache exploded, killing 12 people and injuring 62, two of whom remained in critical condition on Tuesday.
The blast devastated the country's largest power plant, just a few hundred metres (yards) away, causing power outages at the height of summer, when afternoon temperatures can easily pass 40 degrees Celsius (104 Fahrenheit).
The Vassiliko plant, which accounted for almost 60 percent of the island's electricity supply, is expected to remain out of operation for many months.
The commander of Cyprus's navy, Andreas Ioannides, was among the dead, as was the commander of the Evangelos Florakis naval base, Lambros Lambrou.
Four other members of the armed services, including 20-year-old twin brothers, and six fire fighters also died.
The presidential palace, which was the governor's residence during British colonial times, now just houses offices and conference rooms, and is used for ceremonial purposes. The country's presidents do not live there.
Yet the highly symbolic compound was guarded by a handful of police in riot gear.
After unsuccessfully urging the police to join them, a witness said some youths broke a small lock on the gate and and the crowd poured in. The police stepped aside and let them pass, up a drive way to another gate, which was blocked by more police with gas masks.
After more than half an hour of chanting, and again urging the police to join them, the crowd of old and young, men and women, began to disperse.
CLASHES NEAR PALACE
Outside, from a newly landscaped roundabout with a lone olive tree and covered with rocks, a handful of youths started hurling the stones at the compound, and police responded with tear gas.
There were no immediate reports of arrests or injuries, but some people were overcome by the tear gas.
There was a smaller march in the coastal city of Larnaca, with demonstrators carrying a banner that asked "Why? Why? Why?"
"We want Christofias out, because he's responsible for all this and we are very angry," one of the Nicosia demonstrators, Petros Pavlopoulos, told AFP.
The media were also in no doubt that the blast was avoidable and that the government had a lot of unanswered questions to answer.
"It's a crime," screamed the front-page headline in pro-opposition daily Alithia (The Truth).
It said small explosions were recorded at the base several days before the killer blast, but pleas from navy commander Ioannides to remove the containers were ignored.
The English-language Cyprus Mail called it a "criminal error," while squarely putting the blame on Christofias.
The paper said in an editorial that it was a "disaster that could have been avoided if our country was run by a less incompetent president."
The independent Politis daily ran with the headline: "Criminals: 12 dead and the economy in darkness because of criminal apathy."
At a news conference, government spokesman Stefanos Stefanou was asked why the government had not got rid of the cache of shipping containers, which had been seized under Western pressure from a ship travelling to Syria from Iran and was piled in the open and exposed to the elements.
The official Cyprus News Agency said he told journalists the "position of the government... was the material not to be kept in Cyprus, so it made specific proposals to the Security Council and other countries involved."
However, he said none of the government's efforts were successful.
The EAC said Tuesday various areas across the island would be hit by rolling two-hour power cuts, but that every effort would be made to assure uninterrupted supplies to airports, ports, hospitals, and industrial and tourist areas.
The Cyprus Energy Regulatory Authority issued a decree making it compulsory to use generators where available.
Meanwhile, Commerce Minister Antonis Paschalides said talks were underway with Greece and Israel to obtain mobile generators to help the resort island cope with the peak holiday season.
