Norwegian national Mikael Davud, a member of China's Uighur minority considered the mastermind behind the plot against the Jyllands-Posten daily, was sentenced to seven years behind bars.
Shawan Sadek Saeed Bujak, an Iraqi Kurd residing in Norway, meanwhile received a three-and-a-half-year prison term.
According to the prosecution, the two men had in liaison with Al-Qaeda planned to use explosives against the offices of the Danish newspaper and to murder Kurt Westergaard, the cartoonist behind the most controversial of the 12 drawings of the Muslim Prophet published in September 2005.
Westergaard's drawing, which has earned him numerous death threats and an assassination attempt, showed Muhammad wearing a turban shaped like a bomb with a lit fuse.
The prosecution had demanded prison sentences of 11 and five years respectively.
"There is no doubt that it was Davud who took the initiative in the preparations for a terrorist act and that he was the central character," the three judges said in their ruling.
"The court also believes that it was he himself who would have carried out the terrorist attack since he has explained that he planned to lay out the explosives himself," they added.
The judges also said the prosecution had proven "beyond any doubt that Davud knowingly and voluntarily plotted with Al-Qaeda to carry out a bomb attack against Jyllands-Posten with a bomb that was so powerful that he understood human life could be lost."
The court did not however find it proven that the men had planned to assassinate Westergaard.
According to Norway's intelligence service PST, Davud, a short, bearded 40-year-old, received training in making and using explosives from Al-Qaeda members and sympathisers in Pakistan's region of Waziristan between November 2008 and July 2010.
Jyllands-Posten's publication of the 12 cartoons of the prophet Muhammad provoked violent and even deadly protests across much of the Muslim world.
On Monday, the Danish paper refused to comment on the verdict in Oslo.
David Jakobsen, an Uzbek arrested at the same time as Davud and Bujak in July 2010, was meanwhile acquitted Monday of the most serious charges but was sentenced to four months behind bars for helping the two others to procure the materials needed to create the explosives.
The three men had all pleaded not guilty to the charges when the trial opened and their lawyers asked for their acquittal.
Davud however did confess to planning an attack, but said it was directed at Chinese interests in Norway and not at Jyllands-Posten.
The member of the oppressed Uighur minority in China said he had been acting out of purely personal motives and that he had manipulated the two others so they would help him get hold of chemicals, including hydrogen peroxide, that he needed to build a bomb.
Bujak, 39, meanwhile admitted that he had spoken with Davud about the possibility of punishing Jyllands-Posten for the cartoons, but insisted the comments were vague and did not constitute a terrorist plot.
"Bujak helped Davud with the preparations ... and there is no doubt that he was very much involved," the judges ruled, nonetheless lending credence to his insistence he had had no intention of participating in the attack itself.
As for Jakobsen, who contacted police voluntarily in November 2009 and was the only one of the three to have been released from custody until the verdict, he categorically denied any intention to participate in the plot.