The men had been charged with one count of terror crimes and two counts of violating weapons laws.
The three Swedish nationals and one Tunisian living in Sweden had pleaded not guilty to the terrorism charges, but a district court found all four "guilty of terrorism", chief judge Katrine Eriksen said in the unanimous verdict, which was broadcast live.
However Sahbi Ben Mohamed Zalouti, Munir Awad and Omar Abdalla Aboelazm -- all Swedish citizens of Tunisian, Lebanese and Moroccan origin, respectively -- and Tunisian national Mounir Ben Mohamed Dhahri were found not guilty of a secondary charge of weapons possession due to a technicality, she said.
Prosecutors had asked that the four, aged 31 to 46, be sentenced to between 14 and 16 years in prison -- which would have been a historically severe sentence in this kind of case in Denmark.
Prosecutor Gyrithe Ulrich insisted to Jyllands-Posten on Monday that "this case is different from other cases and should result in a stricter penalty.
"They were close to carrying out (the attack). This was not just initial preparations as we have seen in other cases," she said.
"In this case we were very close."
But the court in the Copenhagen suburb of Glostrup opted instead Monday to hand the four 12 years behind bars, on a par with two other sentences handed down to date in cases involving terrorism plots.
Both sides have 14 days to appeal the verdict and sentencing.
"We are very satisfied with the result of 12 years," Ulrich said after the sentencing, adding that she had yet to decide whether to appeal.
Awad, Abdalla Aboelazm and Dhahri were arrested in Copenhagen on December 29th, 2010.
The men were based in Sweden and had travelled over to Denmark by car the night before they were arrested in a flat in the Herlev district of the Danish capital.
A fourth, Mohamed Sahbi Zalouti, who had abandoned the group in Jönköping in central Sweden, was later arrested at his apartment in the north Stockholm suburb of Järfälla.
He was subsequently extradited to Denmark.
Prosecutors had charged that the the four planned to "kill a large number of people" at the Jyllands-Posten's offices in Copenhagen when they were arrested on December 29, 2010.
The daily paper in 2005 published a dozen cartoons of Islam's founding prophet that triggered violent and sometimes deadly protests around the world.
A machine gun with a silencer, a revolver, 108 bullets, 200 plastic handcuff strips 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, said they swooped on them just after hearing them say they were going to the newspaper office.
The four all adamantly denied the terrorism charge, but Dhahri pleaded guilty to arms possession.
Prosecutors said during the trial that the target of the suspected plot was likely an award ceremony celebrating the "Sporting Newcomer of the Year" at the Jyllands-Posten building.
In addition to a number of sports celebrities, Danish Crown Prince Frederik was present at the ceremony, but prosecutors said the four did not appear to have known he was there and that he was probably not their target.
The court was set to hand down its sentence later Monday. The four risk up to 16 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.