Relatives of some passengers were given the news at Merida airport
Wreckage of the plane was found early on Friday just 10km (six miles) north-east of the city of Merida.
It had taken off from the western city shortly before dusk on Thursday and on a flight to the capital, Caracas.
President Hugo Chavez said Venezuela was in mourning and called for a full investigation into the incident.
The mostly Venezuelan victims among the 43 passengers and three crew members included three Colombians and a US citizen.
Wall of rock
"The impact was direct. The aircraft is practically pulverised," firefighter Sgt Johnny Paz told the Venezuelan TV station Globovision.
They have given us the news that there's nothing there, that there are no survivors
Olivia Gil,
relative of victim
"It crashed at an altitude of 12,000 feet (4,000 metres) against a wall of rock," he said. "There are no survivors."
The area's mountainous terrain has made reaching the wreckage difficult.
"The plane is just too destroyed and it is in such a tough area," said Gerardo Rojas, a regional civil defence chief.
Only the tail of the twin-engine ATR-42 plane, operated by the Santa Barbara airline, was visible from the air.
Rescuers abseiled down from helicopters to search the wreckage.
Other search parties had been sent on Thursday night by foot.
Difficult to navigate
At Simon Bolivar airport in Caracas, where the plane had been due to arrive, relatives of victims received support from psychiatrists having been informed there were no survivors.
Merida is located about 680km (420 miles) south-west of Caracas.
It is notoriously difficult to navigate around the city.
Pilots are given special training to take off and land at the airport because the city is surrounded by high mountains.
Visibility is often poor and planes are not allowed to take off at night.
However, the weather on departure was said to have been normal for Merida.
No distress call was reported from the pilot.
The crashed plane was a turboprop aircraft produced by ATR, a French-Italian company.
Santa Barbara airline's president, Jorge Alvarez, said the plane had been well maintained and had no history of technical problems.
The plane was about 20 years old and the pilot had been working for Santa Barbara for eight years, he said.
A Venezuelan plane with 46 passengers onboard has been reported missing in western Venezuela, officials say.

The Santa Barbara Airlines plane took off just before dusk from the city of Mérida en route to Simón Bolívar International Airport outside the capital city of Caracas.

Noel Marquez, director of Venezuela's emergency management agency in Mérida, said the plane has failed to contact control towers. Civil Defense chief General Antonio Rivero told reporters that it is unknown whether or not the plane crashed or is simply missing.

Mérida a town roughly 680 kilometers (422 miles) from Caracas is a popular tourist location.