"The company expresses its deep condolences for the passengers and crew members who died in the plane crash," the airline said in a statement.
The disaster prompted an unusually swift public reaction from President Xi Jinping, who said he was "shocked" and ordered an immediate investigation into its cause.
Hundreds of firefighters were dispatched to the scene in Teng county near Wuzhou, state media reported, as nearby villagers rushed to help the rescue effort.
"Everyone went to the mountains," Tang Min, who runs a restaurant a few kilometres from the crash site, told AFP by telephone.
Fears for the fate of the jet spread on Monday afternoon as local media reported that China Eastern flight MU5735 had not arrived as planned in Guangzhou after taking off from Kunming shortly after 1:00 pm (0500 GMT).
Flight tracking website FlightRadar24 showed no data for the flight after 2:22 pm.
The tracker showed the plane sharply dropped from an altitude of 29,100 feet to 3,225 feet (8,870 to 982 metres) in three minutes, before flight information ceased.
One villager told a local news site that the plane had "completely fallen apart" and he had seen forest areas destroyed by the fire it caused when crashing into the mountainside.
China Eastern changed its website to black and white only on Monday afternoon.
A January company report said China Eastern had 289 Boeing 737-series aircraft in its 751-strong fleet.
State broadcaster CCTV said it had learned that China Eastern will ground all its 787-800 jets as a precaution after the crash.
Boeing said in a statement that it was "aware of the initial media reports and... working to gather more information".
Xi called for "all efforts" towards the rescue and to find out the "cause of the accident as soon as possible", according to CCTV.
"We are shocked to learn of the China Eastern MU5735 accident," he said, calling for "the absolute safety of the sector and people's lives".
The arrivals board at Guangzhou airport showed the jet's flight information for hours after it had crashed, as staff in full PPE held up signs to direct distraught relatives to a separate area that had been set up to receive them.
One relative waiting in Guangzhou airport told local media that she had been due to board the flight, but had changed her booking at the last minute to an earlier plane.
Her sister and four friends had taken the crashed plane, she added. Now she was just "waiting for news", she said. "I feel very sad."
A villager near the crash site surnamed Liu told state-run China News Service that he had driven a motorbike to the scene after hearing a loud explosion.
He said he saw debris on the ground, including an aircraft wing and fragments of clothing hanging from trees.
China had enjoyed an enviable air safety record in recent years as the country was crisscrossed by newly built airports and serviced by new airlines established to match breakneck growth over the last few decades.
A Henan Airlines flight crashed in northeastern Heilongjiang province in 2010, killing at least 42 out of 92 people on board, although the final toll was never confirmed. It was the last Chinese commercial flight crash that caused civilian casualties.
The deadliest Chinese commercial flight crash was a China Northwest Airlines crash in 1994, which killed all 160 onboard.
Jean-Paul Troadec, former director of the Bureau of Enquiry and Analysis for Civil Aviation Safety, told AFP it was "far too early" to draw conclusions, but added that the Flightradar data was "very unusual".