Mikael Davud, a Norwegian of Uighur origin, Shawan Sadek Saeed Bujak, an Iraqi Kurd residing in Norway, and David Jakobsen, an Uzbek also living in Norway, have been charged with "conspiracy to commit a terrorist attack in northern Europe".
The three, who were arrested in July 2010, have also been charged with possession of materials used to make explosives. Police found hydrogen peroxide and acetone stored in a cellar belonging to one of them.
According to the prosecution, the trio are suspected of planning and preparing an attack against the newspaper Jyllands-Posten and/or the caricaturist Kurt Westergaard.
Westergaard, 76, drew the most controversial of the 12 cartoons, featuring the Prophet Muhammad with a lit fuse in his turban, which were published in 2005 and later touched off a wave of sometimes violent protests around the Muslim world.
"They risk up to 20 years in prison," prosecutor Geir Evanger told AFP.
"Our closing arguments will illustrate the gravity of the charges," he said.
Norway's intelligence agency PST also suspects the trio of having ties to the Al-Qaeda network.
Davud, 40, presented as the mastermind, was trained in explosives handling at an Al-Qaeda camp in Pakistan, according to PST.
Davud and Bujak, 38, have been held in custody since their arrest and have both admitted they were planning an attack though their versions have differed on the target.
Davud, a member of the Chinese Uighur minority, has said the target was the Chinese embassy in Oslo while Bujak said it was the Jyllands-Posten newspaper.
The third man, David Jakobsen, who contacted police voluntarily, has denied any responsibility and is currently a free man.
The trial opens less than two weeks after the offices of French satirical weekly Charlie Hebdo were firebombed in Paris as it published an edition featuring the prophet Mohammed as "guest editor" on the cover.
The identity and motive of the firebombers have not been proven but glances have been cast at extremist Muslims.
Since 2005, Jyllands-Posten and Westergaard have been the target of numerous threats from Islamist circles.
At the end of December 2010, Danish intelligence said they had foiled an Islamist plot against the newspaper and five people were arrested in Denmark and Sweden.
Westergaard now lives with round-the-clock security.
He was the victim of a murder attempt in January 2010 when an axe-wielding man burst into his home, and he has also received several death threats.
The man who tried to kill him, Mohamed Geele of Somalia, has been sentenced to 10 years in prison by a Danish court.
In September, Westergaard was forced to cut short a trip to Oslo after Norwegian intelligence caught wind of a possible attack against him.