Until recently, evidence of Neanderthal cave use in the Algarve (Southern Portugal) came only from the site of Ibn Ammar. Over the last couple of years, archaeological excavations inside another cave, Gruta da Companheira, yielded Mousterian stone tools associated with possible human fossils. The discovery of this assemblage is groundbreaking because it may contribute to enlighten the Neanderthal/cave relationship and explain the dearth of similar sites in the Algarve. Gruta da Companheira, however, is a complex karst system, which was partly destroyed during its accidental discovery. As result, the original entrance of the cave remains unknown, and it is unclear how sediments, archaeological materials and Neanderthals accessed the site. To tackle these issues, we combined geomorphological observations with speleological, Electrical Resistivity Tomography (ERT) and Ground-Penetrating Radar (GPR) prospections. Our data indicate that Gruta da Companheira was probably accessed from the hilltop through a sub-vertical entrance. Additionally, our results suggest the existence of yet unexplored shallower cavities connected with the already known passages of Gruta da Companheira. These results will guide the opening of new excavation areas at the site. The limestone bedrock hosting Gruta da Companheira has been extensively dissolved by karst processes. Therefore, it is necessary to focus future research on the cave infillings to clarify whether Neanderthals exploited the cave’s inner chambers or alternatively limited their occupations to the hilltop and geogenic processes reworked their materials into the endokarst system shortly after their stays. The deep karstification and partial collapse of the hill hosting Gruta da Companheira are common in limestone outcrops that occur throughout the Western Algarve. Poor visibility and poor accessibility of this karst area, densely covered with shrubby vegetation, are factors that need to be considered when addressing the scarcity of Middle Palaeolithic cave sites in this region.