French fighter jets, U.N. peacekeepers and others hunted for signs of wreckage of the MD-83 plane in the remote region, where scattered separatist violence may hamper the search and any eventual investigation into what happened.
Families from France to Canada and beyond waited anxiously for signs of Flight 5017 and their loved ones aboard. Nearly half of the passengers were French, many en route home from Africa.
The plane, owned by Spanish company Swiftair and leased by Air Algerie, disappeared from radar screens less than an hour after takeoff, en route from Burkina Faso's capital of Ouagadougou to Algiers.
"Everything allows us to believe this plane crashed in Mali," French President Francois Hollande said after an emergency meeting in Paris. He said the crew changed its flight path because of "particularly difficult weather conditions."
Earlier, French Foreign Minister Laurent Fabius told reporters the plane "probably crashed" and no "trace of the aircraft has been found."
His face drawn and voice somber, Fabius added, "If this catastrophe is confirmed, it would be a major tragedy that hits our entire nation, and many others."
Conflicting reports emerged about wreckage spotted in two different sites, several hundred kilometers (miles) away from each other in the sparse, vast region where the Sahara Desert meets the rest of Africa.
Malian Communiciations Minister Mahamadou Camara told The Associated Press on Thursday night that the plane hadn't yet been found and "the search is underway." French military and diplomatic officials also said no wreckage had been found.
Before vanishing, the pilots sent a final message to ask Niger air control to change its route because of heavy rain, Burkina Faso Transport Minister Jean Bertin Ouedraogo said.
A resident who lives in a village in Mali about 80 kilometers (50 miles) southeast of the town of Gossi said he saw a plane coming down early Thursday, according to Gen. Gilbert Diendere, heading the crisis committee set up in Burkina Faso.
"We think that it is a reliable source because it corresponds to the latest radar images of the plane before it lost contact with air controllers," Diendere said.
Radar images show the plane deviated from its route, Diendere said. Gossi is nearly 200 kilometers (175 miles) southwest of Gao.
The French president said "all military means we have in Mali" were being activated for the search, through the night if needed. France has considerable military resources there because of its intervention that began in January 2013 to rout al-Qaida-linked extremists who were controlling the north.
The U.N. peacekeeping mission in Mali, known as MINUSMA, was helping in the search, U.N. deputy spokesman Farhan Haq said.
Algerian Transport Minister Omar Ghoul, whose country's planes were also searching for wreckage, described it as a "serious and delicate affair."
The vast deserts and mountains of northern Mali fell under control of ethnic Tuareg separatists and then al-Qaida-linked Islamic extremists after a military coup in 2012.
The French-led intervention scattered the extremists, but the Tuaregs have pushed back against the authority of the Bamako-based government. Meanwhile, the threat from Islamic militants hasn't disappeared, and France is giving its troops a new and larger anti-terrorist mission across the region.
A senior French official said it seems unlikely that fighters in Mali had the kind of weaponry that could shoot down a jetliner at cruising altitude. While al-Qaida's North Africa branch is believed to have an SA-7 surface-to-air missile, also known as MANPADS, most airliners would normally fly out of range of these shoulder-fired weapons. They can hit targets flying up to roughly 12,000-15,000 feet.
The disappearance of the Air Algerie plane comes after a series of aviation disasters.
Fliers around the globe have been on edge ever since Malaysia Airlines Flight 370 disappeared in March on its way to Beijing. Searchers have yet to find a single piece of wreckage from the jet with 239 people on board.
Last week, a Malaysia Airlines flight was shot down while flying over a war-torn section of Ukraine, and the U.S. has blamed it on separatists firing a surface-to-air missile.
Earlier this week, U.S. and European airlines started canceling flights to Tel Aviv after a rocket landed near the city's airport. Finally, on Wednesday, a Taiwanese plane crashed during a storm, killing 48 people.
It's easy to see why fliers are jittery, but air travel is relatively safe.
There have been two deaths for every 100 million passengers on commercial flights in the last decade, excluding acts of terrorism. Travelers are much more likely to die driving to the airport than stepping on a plane. There are more than 30,000 motor-vehicle deaths in the U.S. each year, a mortality rate eight times greater than that in planes.
The Air Algerie jet had been missing for hours before the news was made public. It wasn't clear why airline or government officials didn't release information earlier.
Swiftair, a private Spanish airline, said the plane was carrying 110 passengers and six crew, and left Burkina Faso for Algiers at 0117 GMT Thursday (9:17 p.m. EDT Wednesday), but had not arrived at the scheduled time of 0510 GMT (1:10 a.m. EDT Thursday). It said the crew included two pilots and four flight attendants.
The passengers include 51 French, 27 Burkina Faso nationals, eight Lebanese, six Algerians, five Canadians, four Germans, two Luxembourg nationals, one Swiss, one Belgian, one Egyptian, one Ukrainian, one Nigerian, one Cameroonian and one Malian, Ouedraogo said. The six crew members are Spanish, according to the Spanish pilots' union.
Swiftair said the plane was built in 1996 and has two Pratt & Whitney JT8D-219 PW engines.
Swiftair took ownership of the plane on Oct. 24, 2012, after it spent nearly 10 months unused in storage, according to Flightglobal's Ascend Online Fleets, which sells and tracks information about aircraft. It has more than 37,800 hours of flight time and has made more than 32,100 takeoffs and landings.
If confirmed as a crash, this would be the fifth one - and the second with fatalities - for Swiftair since its founding in 1986, according to the Flight Safety Foundation.
The MD-83 is part of a series of jets built since the early 1980s by McDonnell Douglas, a U.S. company now owned by Boeing Co. The MD-80s are single-aisle planes that were a workhorse of the airline industry for short- and medium-range flights for nearly two decades. As jet fuel prices spiked in recent years, airlines have rapidly being replacing the jets with newer, fuel-efficient models such as Boeing 737s and Airbus A320s.
There are 496 other MD-80s being flown, according to Ascend.
Boeing spokesman Wilson Chow said the company was aware of the reports on the plane and was "gathering more information."
Brahima Ouedraogo reported from Ouagadougou, Burkina Faso. AP journalists Ciaran Giles in Madrid, Spain, Elaine Ganley, Thomas Adamson and Sylvie Corbet in Paris, and Edith M. Lederer at the United Nations contributed to this report.