There were few clear indications of what might have happened to the aircraft, or whether there were casualties, but Burkino Faso Transport Minister Jean Bertin Ouedrago said it asked to change route at 0138 GMT because of a storm in the area.
"I can confirm that it has crashed," the Algerian official told Reuters, declining to be identified or give any details about what had happened to the aircraft on its way north.
Almost half of the passengers were French citizens, an airline official said.
Two French fighter jets based in the region have been dispatched to try to locate the airliner along its probable route, a French army spokesperson said.
Niger security sources said planes were flying over the border region with Mali to search for the flight.
Algeria's state news agency APS said authorities lost contact with flight AH 5017 an hour after it took off from Burkina Faso, but other officials gave differing accounts of the times of contact, adding to confusion about the plane's fate.
Swiftair, the private Spanish company that owns the plane, confirmed it had lost contact with the MD-83 operated by Air Algerie, which it said was carrying 110 passengers and six crew.
A diplomat in the Malian capital Bamako said that the north of the country - which lies on the plane's likely flight path - was struck by a powerful sandstorm overnight.
Whatever the cause, another plane crash is likely to add to nerves in the industry after a Malaysia Airlines plane was downed over Ukraine last week, a TransAsia Airways crashed off Taiwan during a thunderstorm on Wednesday and airlines cancelled flights into Tel Aviv due to the conflict in Gaza.
An Air Algerie representative in Burkina Faso, Kara Terki, told a news conference that all the passengers on the plane were in transit, either for Europe, the Middle East or Canada.
He said the passenger list included 50 French, 24 Burkinabe, eight Lebanese, four Algerians, two from Luxembourg, one Belgian, one Swiss, one Nigerian, one Cameroonian, one Ukrainian and one Romanian.
Lebanese officials said there were at least 10 Lebanese citizens on the flight.
A spokesperson for SEPLA, Spain's pilots union, said the six crew members were from Spain. She could not give any further details.
Regional search
Swiftair said on its website the aircraft took off from Burkina Faso at 0117 GMT and was supposed to land in Algiers at 0510 GMT but never reached its destination.
An Algerian aviation official said the last contact Algerian authorities had with the missing Air Algerie aircraft was at 0155 GMT when it was flying over Gao, Mali.
Aviation authorities in Burkina say they handed the flight to the control tower in Niamey, Niger, at 1:38am (0138 GMT). They said the last contact with the flight was just after 4:30am (0330 GMT).
Burkina Faso minister Ouedrago said the flight asked the control tower in Niamey to change route at 0138 GMT because of a storm in the Sahara.
However, a source in the control tower in Niamey, who declined to be identified, said it had not been contacted by the plane, which in theory should have flown over Mali.
Burkinabe authorities have set up a crisis unit in Ouagadougou airport to provide information to families.
Issa Saly Maiga, head of Mali's National Civil Aviation Agency, said that a search was under way for the missing flight.
"We do not know if the plane is Malian territory," he told Reuters. "Aviation authorities are mobilised in all the countries concerned - Burkina Faso, Mali, Niger, Algeria and even Spain."
Aviation websites said the missing aircraft, one of four MD-83s owned by Swiftair, was 18-years-old. The aircraft's two engines are made by Pratt & Whitney, a unit of United Technologies.
US planemaker McDonnell Douglas, now part of Boeing, stopped producing the MD-80 airliner family in 1999 but it remains in widespread use.
According to British consultancy Flightglobal Ascend, there are 482 MD-80 aircraft in operation, many of them in the United States.
"Boeing is aware of the report (on the missing aircraft). We are awaiting additional information," a spokesperson for the planemaker said.
Swiftair has a relatively clean safety record, with five accidents since 1977, two of which caused a total of eight deaths, according to the Washington-based Flight Safety Foundation.
Air Algerie's last major accident was in 2003 when one of its planes crashed shortly after take-off from the southern city of Tamanrasset, killing 102 people.
In February this year, 77 people died when an Algerian military transport plane crashed into a mountain in eastern Algeria.
COMMENTS (12)
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ
Travelling by air have become more riskier than last year.
"NOT" a flying season.
Rising prices and crashing planes . What a paradox !
the rate at which air crafts are reportedly crashing internationally is undoubtedly alarming.
not sure whether it has to do with rows between Boeing and Airbus, or whether suddenly the staff responsible for each aircraft's safety prior to its take-off has become careless.
frankly, these incidents are not only fishy but also very critical because precious civilian lives are being lost. Whether its the Airline industry itself trying to make an international point, or whether some of the most powerful agencies in the world are involved in bringing down the once considered safest travel industry for some twisted reason - is something that will clear up in a few years. nevertheless, IATA and Civil Aviation Authorities of the entire world need to take extra-ordinary measures before the Air travel industry loses its credibility.
God almighty .. Where are thou ? Looks like the gods have conspired against us poor hapless earthlings . Crash after crash ... Add possible shoot downs by militants and crashes to the existing list of things to be wary of while flying - turbulence , air pockets , crash landing ...
Don't take any chance cancel your flight..
The horrifying moment when u read such report at an airport...
scary news. More flights more accidents. or too much media too information?
One of the worst year for aviation industry.....
What is happening with the planes...? I need to get on one in less than 24 hours...!!!!
Whats happening with planes?