A Sedella le ocurre igual que a todos los pueblos de la Axarquía, ya que es muy probable que su poblamiento tenga orígenes muy antiguos y que fuese conocida por los romanos, a juzgar por los restos encontrados: monedas, cerámica, etc. Posiblemente su nombre venga del término latino sedilia que en el Bajo Imperio significaba emplazamiento o posesiones rurales. En el siglo VII, antes de la llegada de los árabes, aparece citada en el mapa de obispados mandado hacer por el rey visigodo Wamba, con el nombre de Sedille, y anteriormente por el obispo malagueño Teodulpo en su congregación episcopal como Sedilla. Después de la conquista cristiana en 1487 se le llama Xedalia. Aunque, según la tradición popular, la denominación data de la época de la Reconquista, cuando en el paraje denominado Arroyo de la Matanza hubo un combate entre cristianos y musulmanes y al referírsele a la reina Isabel cómo fue dicha batalla, respondió: “Sé de ella”. También era conocida como Villa Castillo, debido a que en una de las alturas próximas al actual pueblo se encuentran las ruinas de una gran fortaleza, a cuyos pies se asentaría un minúsculo núcleo urbano. Sirvió dicho castillo de sede al señor de aquella zona, el último de los cuales fue don Diego Fernández de Córdoba, al que los Reyes Católicos otorgaron en propiedad la villa y fortaleza y que posteriormente le fueron cambiadas por la villa de Comares, por la reina Doña Juana en 1512. También se conserva un documento expedido en 1514 por la misma reina Doña Juana y firmado por su padre Fernando V y el Concejo, por el cual se nombran diez testigos de Sedella y otros diez de Comares, para que junto al bachiller Juan de Salmerón, comprueben por dónde van los límites de cada una de las villas para proceder al deslinde de los términos, lo que hace suponer que habrían surgido problemas entre los vecinos de Comares y Sedella a la hora de disponer de sus respectivas propiedades. Durante la rebelión morisca fue una de las primeras poblaciones que se levantaron en armas ya que uno de los cabecillas más destacados en esta zona fue un monfí de la villa. Después de sofocada la rebelión sus tierras fueron repobladas con cristianos viejos de Carmona y de la Mancha.