Sahbi Ben Mohamed Zalouti, Munir Awad and Omar Abdalla Aboelazm, all Swedish citizens of Tunisian, Lebanese and Moroccan origin respectively, along with a Tunisian national living in Sweden, Mounir Ben Mohamed Dhahri, face charges of "attempted terrorism."
Prosecutors say the four were plotting to "kill a large number of people" at the Jyllands-Posten daily's offices in Copenhagen when they were arrested on December 29, 2010.
Jyllands-Posten published a dozen cartoons in 2005 of Islam's founding prophet that triggered violent and sometimes deadly protests around the world.
A machine-pistol with a silencer, a revolver, 108 bullets, reams of duct tape and $20,000 were among the items found in the men's possession when they were arrested.
Danish police, who had been collaborating with their Swedish counterparts and had been wiretapping the men, swooped just after hearing them say they were "going to" the newspaper office.
In Glostrup district court on Friday the four accused all denied the terrorism charge, but Dhahri did plead guilty to arms possession.
Prosecutor Gyrithe Ulrich revealed however that Zalouti had told Swedish police in an interrogation in January last year that the three men arrested in Denmark had gone there to carry out an attack, according to public broadcaster DR.
Zalouti was arrested near Stockholm the same day as the other three in a Copenhagen suburb.
Ulrich played a tape of the police questioning, in which Zalouti said the three others had tried to include him in their plan, but that he had refused and had got out of the car in Joenkoeping, long before they reached Denmark.
On Friday, though, Zalouti insisted he and the others had not discussed carrying out an attack.
"We had spoken about a possible attack in Denmark, but not that we would carry it out," he told the court, according to DR, insisting he had been planning to drive to Gothenburg to work and did not know the others were headed for Copenhagen.
A second prosecutor, Henrik Plaehn, said that a ceremony celebrating the Sporting Newcomer of the Year at the Jyllands-Posten building was likely the target of the suspected plot.
In addition to a number of sports celebrities, Danish Crown Prince Frederik was present at the ceremony.
"It appears this event was the target," Plaehn said, according to Jyllands-Posten, stressing though that the prosecution did not know if the four accused were aware the prince was there and did not think they had been after him.
Plaehn also argued there was evidence the plot had links to Pakistan, but said he would provide more details later in the trial, which is set to last until June.
At least one of the men is known to have international ties: Awad has been arrested twice before abroad suspected of terrorist links, Sweden's foreign ministry told AFP last year.
He was arrested in Somalia by Ethiopian troops in 2007 and again in Pakistan two years later, when he was travelling with his wife, their two-year-old son and Mehdi Ghezali, a Swede who had spent two years at Guantanamo Bay.
The prosecution has not yet said what penalty it will be seeking beyond a request that the four after serving their sentences be expelled from Denmark and never allowed to return.
According to DR, however, they all risked "a historically severe punishment," with up to 14 years behind bars.
Jyllands-Posten has been the target of a string of attempted and plotted attacks, and remains a top target for Islamic extremists, Danish intelligence service PET said at the end of January.
