La reconquista de Benalmádena por parte de los ejércitos cristianos, al mando del rey Enrique IV, se produce en el año 1456 con la consiguiente destrucción de todo cuanto se encontraron a su paso. De hecho, muchos vecinos de Benalmádena se refugian en Mijas para posteriormente tratar de reconstruir parte de lo que fue su pueblo, que vuelve a ser destruido en 1485, esta vez por las tropas de Fernando el Católico.
Desde ese momento, llegan momentos oscuros en la historia de Benalmádena, en un terreno que por inseguro nadie quiere habitar. Es así que en 1491 el rey encarga a Alonso Palmero la repoblación de Benalmádena con 30 familias cristianas cosa que no consigue debido a diversos avatares, entre los que se encuentra un terremoto que hace huir a los recién llegados.
El primer censo oficial de población de Benalmádena data de 1496 y nos indica que los vecinos que lo integran son 10 caballeros, incluido en ellos el alcaide Alonso Palmero, y 21 peones cabeza de familia.
Los problemas de poblamiento de Benalmádena tienen su origen en la inseguridad de la costa, asaltada habitualmente por enemigos (especialmente de berberiscos recién expulsados de este territorio) y piratas que llegan a la búsqueda de riquezas ya inexistentes.
A mediados del siglo XVI Benalmádena cuenta con 10 familias y unos 50 habitantes y es cuando comienza un incipiente asentamiento de la población gracias al espaciamiento de los ataques y que estos tienen otros objetivos. Comienza una actividad comercial que se lleva a cabo fundamentalmente con Mijas ya que Málaga, el principal centro urbano de la costa, dista mucho más y presenta el inconveniente serio de tener que cruzar el río Guadalhorce, el cual era necesario vadear.
De esta época data una de las familias más largamente asentadas en Benalmádena, los Zurita Zambrana, propietarios de grandes parcelas de tierra en la zona de Arroyo de la Miel, donde concentraron un gran patrimonio.
El nombre de la población, mediante la adaptación del vocablo árabe, pasa a ser 'Benalmaina', que es como aparece reconocida durante este periodo.
Posiblemente uno de los peores momentos de la historia de nuestro pueblo se produce el 9 de octubre de 1680 cuando un terremoto no deja una sola casa en pie y echando abajo algunas colinas y que fue empeorado por un maremoto posterior que inutilizó las barcas y arruinó la costa.
En 1784 el genovés Félix Solecio compra el cortijo de Arroyo de la Miel con la intención de construir 6 fábricas de papel (papel blanco y de estraza) para proveer a las fábricas de naipes de Macharaviaya. Si bien las fábricas abandonan su producción en 1806, su infraestructura y viviendas son el origen del actual núcleo urbano de Arroyo de la Miel. A partir de este momento comienza el poblamiento de todo el municipio favorecido por el cada vez más concurrido tráfico comercial entre Málaga y toda la costa.