Los primeros asentamientos humanos en estas tierras se relacionan con el periodo Paleolítico. Tras el paso de la cultura ibérica, que denomina a la localidad Tereses, los romanos fundan la población de Sisapo, situada en la calzada que unía Hispalis con Emerita Augusta. Es posible que a finales del periodo imperial recibiera ya el nombre de Canalia, denominación reutilizada por los árabes siglos más tarde, anteponiéndole "Wad" como indicativo de la presencia de un río. La forma resultante es Wad Al-Kanal. En esta época se explotan las riquezas mineras del subsuelo, aunque la función predominante es la defensiva, con un alcázar natural por su posición. En 1.241, los caballeros de la Orden de Santiago conquistan la localidad para la Corona de Castilla. El rey Fernando III el Santo, como premio, se la entrega a dicha institución. A raíz de ello, se crea el municipio y se les concede a sus habitantes Fuero propio.