More than 90 people were also wounded when two off-road vehicles drove into a crowd in Urumqi, with one of them exploding, the regional government's Tianshan web portal said, in an attack with echoes of a fiery car crash in Tiananmen Square last year.
Pictures posted on Sina Weibo, a Chinese equivalent of Twitter, showed victims lying in a tree-lined street, as others sat on flimsy stools.
Flames rose in the background, while other images showed smoke billowing over market stalls behind a police roadblock. None of the photographs could immediately be verified.
Chinese President Xi Jinping pledged to "severely punish terrorists and spare no efforts in maintaining stability", the official Xinhua news agency reported.
Xinjiang, a vast and resource-rich region in China's far west, has seen periodic violence which has increased and sometimes spread beyond it in recent months.
Beijing says it faces terrorism from a violent separatist movement there, driven by religious extremism and foreign groups, while critics point to economic inequality and cultural and religious repression of Uighurs as causes of unrest.
Tianshan described the attack as a "severe, violent terrorist incident".
"Thugs broke through protective metal barrier by driving two vehicles, colliding with the crowd and detonating explosive devices, causing the deaths of 31 people and injuring 94," it said.
A witness at the market told Xinhua he heard a dozen "big bangs" during the attack, which happened at about 7:50am local time, when Chinese morning markets, which usually sell fresh groceries, are commonly crowded with shoppers.
"There were multiple strong explosions in the morning market at the Cultural Palace in Urumqi," wrote one Weibo poster who said he was less than 100 metres from the scene.
"I saw flames and heavy smoke as vehicles and goods were on fire while vendors escaped leaving their goods behind."
China has seen a series of attacks in recent months targeting civilians that authorities have blamed on separatists from Xinjiang.
On April 30, the final day of a visit by Xi to the region, assailants armed with knives and explosives carried out an attack at a railway station in Urumqi, killing one person and wounding 79. Two attackers also died.
The main plotter had formulated plans from abroad, then eight days before the incident ordered 10 people to make an explosive device and choose a target, Xinhua said in a later report.
In March attackers went on a stabbing spree at a railway station in the southwestern city of Kunming, killing 29 people and wounding 143 in an incident dubbed "China's 9/11" by state media. Four of the assailants were shot dead by police.
In 2009 ethnic riots erupted in Urumqi between Uighurs and the country's majority Han Chinese, leaving 200 people dead and prompting a security crackdown.
China has dramatically increased the number of armed patrols on its streets in response to the spate of violent incidents.
Thursday's blasts came a day after state media reported that courts in Xinjiang jailed 39 people for offences including spreading "terrorist videos".
The 39 were given prison sentences of up to 15 years, the state run China News Service said, adding that several had "organised, led and participated" in terrorist organisations.
Critics say the security threat in Xinjiang is exaggerated by Beijing to justify hard-line measures, and that tensions are driven by cultural oppression, intrusive security measures and immigration by majority Han Chinese which have led to decades of discrimination and economic inequality.
Beijing says that its policies in the region have brought prosperity and higher living standards.
Thursday's attack sparked outrage on Sina Weibo, with many calling for action against the assailants.
"We should learn anti-terrorist methods from the US and Israel which is about talking less nonsense, showing less mercy and killing them all," said one poster.
"Whatever demands they have, they shouldn't hurt innocent people!" said another.
COMMENTS (8)
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ
Very carefully written news. No elaboration no clear mention of attackers. Also not much elaboration that how China is treating them. Also not on frontpage !
@pakistani from lahore: I wish the Chinese people the best of luck and as a Pakistani my heart goes out to them regarding this tragic incident
This seems like A plea to China to not take action on the Muslims, which may extend upto Lahore.Hehehe.
The Uighur nationalists and islamists have the same goal except the nationalist agenda is hijacked by the Islamists, and the line separating them is very narrow, and china policy as in Tibet will not be applicable here.
During the post 9/11 sweep one Uighur nationalist was also captured and sent to gitmo and eventually released and resettled in another country.
Pushed settlement of people never worked historically and locals will resist. It will only make the matters worse. Eg: Baloch resistance to punjab settlers, Palestinian / Israeli conflict, Tamil / singhalese issue .
Very sad to see that this sort of thing is affecting China which is a great and illustrious civilization. I wish the Chinese people the best of luck and as a Pakistani my heart goes out to them regarding this tragic incident
Extermist only handle by prosperity And equality.
31 is not that small number .
Who are these attackers and where did these attackers get their training, will be the first line of inquiry conducted by the Chinese government. Based on those findings the CCP will decide on the course of action.
Look at the comments of their citizen and leaders yet Pakistanis are silent on their best friends Muslim province oppression. And they go on modi bandwagon. Double standards.