El origen de la actual población parece estar en una fortaleza, hoy desaparecida, que sirvió de albergue a diversos señores de la zona, el último de los cuales fue don Diego Fernández de Córdoba. Al pie de la fortaleza debió existir una alquería que los mozárabes llamaban Sedelia o Xedelia.

        Tras la caída de Vélez-Málaga en manos castellanas en 1487, Sedella y las tropas que la guarnecen quedan al cuidado de un alcaide, Juan de Hinestrosa, lo que demuestra su importancia estratégica, convirtiéndose Sedella en una pieza fundamental de la defensa fronteriza junto con Canillas de Aceituno y Córnpeta, que se complementa con las fortalezas de Vélez-Málaga, Bentomiz y Frigiliana.

        La Sedella morisca se ve implicada en la rebelión de 1569 al ser empujados sus habitantes por un monfie (un fuera de la ley) nacido en el pueblo y vecino de Canillas de Aceituno, Andrés el Xorairán, que junto con veinte monfíes más dio el primer asalto el 24 de abril de 1569 a la venta de Pedro Mellado, cristiano que tenía en su poder a la esposa de un moro de la Alpujarra llamado Almueden, que había venido a rescatarla y que fue el que prendió la mecha en una situación que le era propicia a causa de la irritación de los moriscos tras la pragmática de Carlos I de 1 de enero de 1567. La rebelión, como se sabe, tuvo un final trágico en el Peñón de Frigiliana.

        Cuando se crean las parroquias malagueñas en 1505, Sedella es un anexo de Canillas de Albaida, no llegando a ser parroquia propia.

        En 1514, la reina doña Juana nombró a diez vecinos de Sedella como testigos, junto con otros diez de Comares, para que junto con el bachiller Juan de Salmerón comprobasen por dónde iban los límites de cada una de las villas motivo del trueque para proceder al deslinde de los términos de las mismas.