Los primeros ocupantes de los que se tiene constancia en la zona de Benalmádena datan del periodo denominado Solutrense (Paleolítico superior), hace unos 20.000 años, en el que aparecieron numerosos asentamientos humanos en toda la costa de Málaga. En Benalmádena, el yacimiento más representativo de esta época es la Cueva del Toro, ubicada en el monte Calamorro, que según los estudios realizados parece haber sido un santuario. La ocupación de esta cueva data de hace unos 15.000 años y en ella lo más representativo es la existencia de pinturas de color rojo que representan a un bóvido acéfalo. Dada su orientación Sur, con una cómoda entrada y una vista panorámica de toda la zona costera, se trata de un emplazamiento privilegiado para un santuario de dicha época.

La estructura social en el Paleolítico Superior parece estar ligada a grupos familiares que permitieran una fácil movilidad de la población, carente de recursos propios y que utiliza las cuevas como abrigo.

La forma de vida en esta época está ligada a la caza y a la recolección de frutos silvestres. No existen vestigios que demuestren que se practicase ningún tipo de ganadería o cultivo, cosa que ocurre hace unos 5.000 años ya que una mejora climática general permite abordar tareas de cultivo produciéndose un asentamiento más estable de las poblaciones que siguen habitando en cuevas. Nos hallamos ya en el Neolítico.

De esta época existen numerosos restos en el Museo Arqueológico de Benalmádena (instrumentos líticos, cerámicas y ornamentos personales), procedentes de yacimientos locales entre los que destacan las cuevas de La Zorrera y de Los Botijos.