Indonesian Aviation officials say the Trigana Air flight lost contact with ground control at 2:55 PM local time on Sunday as it flew from the regional capital Jayapura to the town of Oksibil in Papua, in the easterm part of Indonesia.
Director General of Indonesia's Aviation Authority, Suprasetyo, says parts of the aircraft have been found not far from its intended landing site at the Oksibil airport.
"According to the information, the Trigana Air aircraft that lost contact was found at Camp 3, Ok Bape District in the Bintang Mountains regency. The information provided by the local residents said that the flight crashed into Tangok mountain. The detail on this finding is still under investigation."
The wreckage has been discovered by villagers, who then alerted officials.
The twin turboprop was carrying 44 adult passengers, five children and five crew.
Bad weather is being pointed to as one of the possible reasons for the crash.
A second plane, which had been sent out to look for the missing one, was forced to turn back because of dangerous flying conditions.
Indonesian transport minister Ignasius Jonan says troops have been sent to the remote mountainous region near Oksibil to continue the search.
"The search will continue today. The officials of the National Search and Rescue Agency will go there with the Air Transportation Director General to facilitate the evacuation work and clarify things to the families of passengers on board."
Trigana Air has had 14 serious incidents since it began operations in 1991, and has lost 10 aircraft.
It has been on a European Union blacklist of banned carriers since 2007.
All but four of Indonesia's certified airlines are on that list.
One of the major concerns is the age of the air fleets in Indonesia.
All aircraft owned by Trigana Air, including the small plane that crashed on Sunday, have been in-use for over 26 years.
Sunday's incident is the latest in a string of aviation disasters in Indonesia over the past year.
In December an AirAsia plane crashed in the Java Sea, killing all 192 people on board.
In July a military transport plane crashed in a residential area of Medan, Sumatra, claiming 140 lives.
The Indonesian government has introduced several new regulations hoping to improve the country's patchy aviation safety record.
For Cri I'm Poornima Weerasekara.
