Nearly 360 miners at the massive Zasyadko mine scrambled to the surface after Sunday's blast, which occurred at a depth of about 1,000 meters (3,300 feet).
Officials gave conflicting accounts of the death toll Monday. Earlier, Emergency Situations Ministry spokesman Mykola Ranha said that 77 miners were killed and 23 were trapped underground, but that figure was later reduced to 72 killed and 28 missing, according to a statement on the ministry's Web site.
The government's industrial safety agency, meanwhile, said 70 were killed and 30 were missing.
One survivor described clambering over the bodies of his co-workers strewn along an underground rail track and navigating through blinding dust to escape.
The hunt for survivors was still under way Monday afternoon, but rescuers were battling a stubborn fire that blocked their path to the tunnel where the missing were believed to be trapped. The tunnel was also blocked by a rock slide triggered by the explosion, emergency officials said.
Above ground in this industrial city in eastern Ukraine, the heart of the former Soviet republic's coal country, flags flew at half-staff as the Donetsk region began three days of official mourning.
Dozens of weeping relatives gathered at the mine's Soviet-era headquarters, waiting anxiously for news of their loved ones. As grim-faced officials emerged to announce the names of the workers found dead, the relatives broke into sobs and cries; some fainted.
Authorities dispatched a team of psychologists to help relatives cope with their grief.
"My son works here. He doesn't answer his mobile phone," a sobbing middle-aged woman told AP Television News. She declined to give her name. "I don't know what's happened. He is not at home. ... He has three little children."
The deadliest accident in Ukraine's coal industry in at least seven years highlighted the lack of attention to safety in a country with some of the world's most dangerous mines.
President Viktor Yushchenko accused his Cabinet on Sunday of not doing enough to reform coal mining, and ordered an official panel to investigate the accident and bring those responsible to account.
Prime Minister Viktor Yanukovych, a native of the mining region, visited the site about 730 kilometers (450 miles) southeast of Kiev, pledging to help victims' families.
Yanukovych, Yushchenko's political rival, suggested the disaster was not caused by safety violations or human error, saying a safety watchdog had reported that miners were working in accordance with norms.
"This accident has proven once again that a human is powerless before nature," he said.
Twenty-eight of the 356 miners evacuated were hospitalized, Ranha said. Earlier, emergency officials had said 367 miners had been evacuated.
Survivor Vitaliy Kvitkovsky recounted a grisly escape.
"The temperature increased sharply, and there was so much dust that I couldn't see anything. ... So I was moving by touch over dead bodies along the rail track," Kvitkovsky said in footage on Channel 5 television.
Experts say Ukraine's mines are dangerous largely because they are so deep, typically running more than 1,000 meters (3,280 feet) underground. Most European coal beds lie at a depth of 500 to 600 meters (1,640 to 1,970 feet).
More than 75 percent of Ukraine's roughly 200 coal mines are classified as dangerous due to high levels of methane, a natural byproduct of mining whose concentration increases with depth.
Mines must be ventilated to prevent explosions, but some rely on outdated ventilation equipment, officials said. Safety violations and negligence add to the problem.
The blast was the deadliest mine accident in Ukraine since an explosion at the Barakova mine in the neighboring Luhansk region killed 81 miners in March 2000.
The Zasyadko mine is one of the biggest and best-paying mines in the region, but salaries are low compared with most of Europe. Natalia Piskun, whose husband was believed trapped underground, said he earned some 2,000 hryvna (US$400; Ђ270) a month, nearly twice the average wage in Ukraine.
But the mine has been plagued by disaster. Last year, a blast there killed 13 workers. In 2002, an explosion killed 20 and 54 died in a similar explosion in 2001. In May 1999, 50 miners were killed in a methane and coal dust blast there.
The mine's office is in central Donetsk, and its kilometers (miles) of shafts and tunnels are sprawled beneath the city. One of its emergency exits is located near a city cemetery used to bury miners killed in accidents here.
Yekaterina Kirichenko, a retired engineer, came to the mine to support a friend whose son was killed. Kirichenko, 73, accused regional authorities of failing to observe safety rules and invest in safety upgrades.
"Our government doesn't care about people, all they need is dollars," Kirichenko said, weeping. "Those oligarchs are building cottages for themselves and pay no attention to the mine. They're killing our children."
Since the 1991 Soviet collapse, more than 4,700 miners in Ukraine have been killed. For every 1 million tons of coal brought to the surface in Ukraine, three miners lose their lives, according to official data.
Despite the dangers, there is growing appetite for Ukraine's rich coal reserves, particularly amid rising natural gas prices. The government has called for production to be increased by a third to 80 million tons this year.