The claim of responsibility came not long after German prosecutors said they had released a man picked up near the scene of the attack, initially suspected of driving the truck.
The man, a Pakistani citizen who came to Germany last year, was taken into custody based on a description from witnesses of a suspect who jumped out of the truck and fled after the attack.
Even before his release, officials had expressed doubt the man was behind the attack.
"We may still have a dangerous criminal out there," warned Berlin police chief Klaus Kandt, whose office urged people to be "particularly vigilant" and report "suspicious movement" using a special hotline.
Though Germany had not seen any successful mass-casualty Islamic extremist attacks until Monday, attempts and recent attacks in neighboring France and Belgium had made many feel it was inevitable.
"We've all been prepared that something like this could happen, so we were not surprised," said economics student Maximilian Much.
The 24-year-old Berliner said the attack hit home because he'd often visited the Christmas market with his girlfriend, but that he wouldn't let himself be led by emotion.
"I'm not going to change my life style now," he said. "The chances that I get killed in a car or bike accident are bigger."
Germany's top prosecutor, Peter Frank, told reporters the attack on the popular market was reminiscent of July's deadly truck rampage in Nice and appeared to follow instructions published by the Islamic State group.
"There is also the prominent and symbolic target of a Christmas market, and the modus operandi that mirrors at least past calls by jihadi terror organizations," Frank said.
In Washington, State Department spokesman John Kirby said the attack "bears the hallmarks of previous terror attacks," but said U.S. officials didn't have enough information to back up the IS claim of responsibility. "There is no direct evidence of a tie or a link to a terrorist organization," he said.
The man arrested near the scene denied any involvement in the attack. Under German law, prosecutors have until the end of a calendar day following an arrest to seek a formal arrest warrant keeping a suspect in custody.
Prosecutors said they decided to release him after turning up no forensic evidence proving he was in the truck's cab during the rampage, and no witnesses who were able to follow him from the scene to where he was picked up.
Among the injured was Inaki Ellakuria, who underwent surgery Tuesday for a broken tibia and fibula on his left leg. He said he knew immediately it was no accident.
"It came fast, too fast to be driving off the road accidentally," the 21-year-old student from Spain tweeted only minutes after the attack. "It has swept me and ran over both of my legs."
Juan Jose Ellakuria told the Associated Press his son also suffered broken bones in his right ankle and instep, as well as damage to his hip.
"He's come out of surgery and he's making good progress," Ellakuria said.
Frank, the German prosecutor, said there were still a lot of unanswered questions.
"We don't know for sure whether it was one or several perpetrators," he said. "We don't know for sure whether he, or they, had support. These investigations aren't concluded yet."
Witnesses saw only one man flee from the truck after it hurtled through the market for 60 to 80 meters (200 to 260 feet) before coming to a stop near the 19th-century church, which was badly damaged in World War II bombing but left standing as a memorial to the destruction of the war.
The head of the Federal Criminal Police Office said authorities had yet to find a pistol that is believed to have been used to kill the Polish truck driver who was supposed to be delivering the steel beams the truck was carrying.
The Polish owner of the truck, Ariel Zurawski, said he last spoke with the driver, his cousin, around noon on Monday and he told him he was in Berlin and scheduled to unload Tuesday morning.
"They must have done something to my driver," he told TVN24.
Flags flew at half-staff on government buildings across the country Tuesday, and in Berlin the national and city flags were projected onto the Brandenburg Gate in tribute to the victims.
Authorities said that in addition to the Polish truck driver, six of the people killed were German but the others have not yet been identified.
Germans have been increasingly wary since two attacks by asylum-seekers last summer were claimed by the Islamic State group. Five people were wounded in an ax rampage on a train near Wuerzburg and 15 were wounded in a bombing outside a bar in Ansbach, both in the southern state of Bavaria. Both attackers were killed.
Those attacks and two others unrelated to Islamic extremism in the same weeklong period, contributed to tensions in Germany over the arrival last year of 890,000 migrants.
Far-right groups and a nationalist party seized on Monday night's attack, blaming Chancellor Angela Merkel for what happened.
"Under the cloak of helping people Merkel has completely surrendered our domestic security," wrote Frauke Petry, the co-chairwoman of the Alternative for Germany party.
The attack also raised concerns of a possible backlash.
"No question, the atmosphere in this country will change and become more tense," said Tarik Elsayed, the 22-year-old German-born son of Egyptian parents.
"Of course, as an Arab I will get more hostile looks, it will get only worse now."
But Tarek Elmasoudi, an Egyptian asylum-seeker, said he wasn't afraid of repercussions. "The Germans are very nice and I want to stay here."
Already under pressure for the huge influx of migrants, Merkel addressed head-on the possibility that an asylum-seeker was responsible for the carnage.
"I know that it would be particularly hard for us all to bear if it were confirmed that a person committed this act who asked for protection and asylum in Germany," she said in a nationally televised statement.
"This would be particularly sickening for the many, many Germans who work to help refugees every day and for the many people who really need our help and are making an effort to integrate in our country."
"Twelve people who were still among us yesterday, who were looking forward to Christmas, who had plans for the holidays, aren't among us anymore," she said. "A gruesome and ultimately incomprehensible act has robbed them of their lives."