The trial, being held under heavy security, comes with Europe still on high alert over fears of jihadist violence following two bloody attacks in Paris in 2015.
Prosecutor Bo Bjerregaard accused the four defendants of trying to “destabilise or destroy Denmark's basic political, constitutional, economic or societal structures”.
The killer, 22-year-old Danish-born Omar El-Hussein, opened fire on February 14 last year outside a cultural centre where the speakers included Swedish artist Lars Vilks, a target of Islamic extremists since he portrayed the Prophet Mohammed as a dog in 2007.
A 55-year-old filmmaker, Finn Nørgaard, died and three people were injured.
Later that night the Dane of Palestinian origin fired six shots outside the city's main synagogue, killing security guard Dan Uzan, 37, and injuring two other people.
The assailant was shot dead by police hours later.
The trial, which is expected to last until September, is to focus on events in the hours between the two attacks, when the four men are accused of having aided the killer.
Bjerregaard said they had to have been aware of the intentions of the gunman, whom some had known since childhood.
After lifting a ban on disclosing their identities, the court named the four as Liban Ahmed Saleban Elmi, 20, Ibrahim Khalil Abbas, 23, Bhostan Khan Hussein, 26 and Mahmoud Rabea, 31.
Bjerregard said earlier this month that charges against a fifth suspect had been dropped.
The prosecution believes the four men are all guilty of committing a “terror offence” by providing El-Hussein with support in the form of ammunition, a hoodie and a bag used in the second attack, and by paying for his time in an Internet cafe where he located the synagogue.
Abbas and Elmi are also charged with helping him get rid of a rifle he used at the cultural centre.
If found guilty, they risk a term of life imprisonment, which in Denmark means they would be entitled to a pardoning hearing after 12 years.
The prosecution, which has set aside 30 court days for the trial over seven months, believes it can show that the four were in close contact with El-Hussein in the hours after the first shooting.
It will have to prove their “intent”, meaning they knew about his plans to commit an act of terror.
Elmi's lawyer told AFP that while her client had been friends with El-Hussein since childhood, he knew nothing of his plans.
“He doesn't deny” meeting up with the gunman on the afternoon of the attacks, “but he denies that he knew anything about terror and he didn't participate in anything concerning terror,” Mette Grith Stage said.
“My client is a Muslim but he wasn't practising very much… I don't see him as radicalised.”
Intelligence agency criticised
Released from prison just two weeks before the attacks after serving time for a stabbing, El-Hussein was known for his violent temper and for having ties to a criminal gang on the immigrant-heavy Mjølnerparken estate where he grew up.
The prosecution told the court he pledged allegiance to the Islamic State group on his Facebook page on the day of the shootings, investigators say he was not part of a jihadist network.
Danish intelligence agency PET has however been criticised for failing to act on information from prison services that he was at risk of radicalisation.
Because the preliminary hearings have been held behind closed doors, little has been known about the four suspects, all of whom are expected to plead innocent.
According to media reports they all have criminal records for offences ranging from break-ins to possession of automatic weapons.
The four appeared solemn as proceedings began, according to an AFP reporter.
One was unshaven and tired-looking, while another, sporting a shaved head, a black hoodie and a black jacket, smiled and shook the hands of two others and his lawyer.
“It has been hard waiting because the police can go out and say to the media what they think of the case but the defence can't do the same,” Hussein's lawyer Berit Ernst told AFP.
Dozens of onlookers queued up outside the courtroom trying to get a seat inside, as about a dozen heavily-armed police guarded the building.
Lawyers for the defence and the families of the victims entered the courtroom without making any comments, while the accused entered from an adjoining jail where they have been held for almost a year.
Prime Minister Lars Løkke Rasmussen warned on the anniversary of the attacks that Denmark still faced a “serious terror threat”.
On Tuesday, police revealed that a 16-year-old Danish girl arrested in January had been planning to bomb two schools, one of which was Jewish.