The caves attracted Palaeolithic and Neolithic man and at the Cueva de la Pileta, cave drawings in both charcoal and paint dating back perhaps 25-30,000 years can be seen. Cueva de la Gato was also home to early man. The pueblo has Phoenician and Roman origins, as suggested by the Roman Ronda to Oba (Jimena) track found in the valley. First century pottery and other artefacts have been excavated near the Benaojan/Montejaque rail station below the village, suggesting Roman origins. With such fertile land, it is not surprising that the Visigoths continued to cultivate the lush green valleys. An inscription and pottery were found in the valley from this period, mentioning the place name of "Bracaris", a name that could have been associated with a hamlet now lost.
Certainly, no large community existed until the Moors established the present town. The name is thought to derive from Bena-Ojan, meaning the children of the Berber tribe Ojan. Others claim the name signifies the House of the Panaderos or baker's house. The pueblo was not isolated; originally, it faced across the river to the now-lost village of Ocegina. Records survive from this period indicating its existence but two other settlements, Comayren and Benare, have also been erased from the landscape.
The village belonged to the kingdom of Ronda during the break-up of the Arabic kingdoms and was closely associated with the neighbouring city. This all ended when the Christians captured Ronda in 1485. A castle seems to have existed and was remodelled by Vasquez Otero into a country retreat. However, his descendants moved the country residence later to Montecorto and Audita and the castle was plundered for building materials.
The military census of 1492 recorded a population of 445, which was the largest in the whole of the region bar Ronda. The population peaked at 549 in 1498, probably as a direct result of the disappearance of outlying communities such as Ocegina. Though the largest community, Benaojan was a junior member of the Senorio de Montejaque, though it acquired its own parish status in 1505, established with one sacrament and beneficiary.
At the time of the expulsion of the Moriscos in 1571, only 60 families lived in the village, suggesting a population decline to around 240. The Christian settlers flourished in these fertile valleys and the population rose to a healthy 1,329 in 1787. This could explain why the Inquisition did not prosecute in the pueblo, as the new community had been well indoctrinated, unlike the outlying villages that were able to maintain their old ways in secret.
The lifeline at the time was based on a mule track that led down to the river via Molino del Santo, or over the mountain to Ronda. The first introduction to the industrial world came with the arrival of the railway in 1892. Road communications were poor and the first car road did not reach the pueblo until 1941, with further communications only established in 1957 when the modern road network was built. At around this period the population was just under 3,000 but the pull of Ronda and the coast has led to a decline and the population now stands at around 1500.