Los orígenes de la ciudad de Niebla se remontan al Neolítico. Se cree que la gruta que fue encontrada en los Bermejales de Niebla, fue habitada por los clanes del hombre del Neolítico; existía allí una especie de taller comercial de objetos de piedra y alguna cerámica cocida al fuego. De este período también quedan vestigios como el Dolmen de la Lobita, al parecer construido por la raza Ligur que habitó el Coto de Doñana.
Sin embargo parece que la fundación de Niebla se debe a los fenicios o los Turdetanos, que utilizaron la palabra “Ilipula” de su lengua de origen como nombre de la ciudad. Otros creen que la fundación de Niebla se debe a los celtíberos. Tras éstos, aparecen los cartagineses, siendo Niebla ya una ciudad estratégica y fortificada. Éstos construyeron un pequeño puerto para seguir el comercio de metales.
Los romanos, al mando de Publio Cornelio Escipión, tras varios intentos y numerosas batallas, consiguieron apoderarse de “Ilipula”. Tras ocuparla los Romanos, la reconstruyen y le permiten incluso acuñar moneda propia en la que aparece el nombre de la ciudad.
Si Niebla fue ciudad romana de gran importancia, en el período visigodo, Electa, alcanzó un alto prestigio religioso y militar, ya que pasó a ser una de las once sedes episcopales de la Bética, cuyo obispado se extendía sobre 300 leguas cuadradas, por lo que es presumible que su límite meridional fuera la desembocadura del Guadalquivir (Medina Sidonia) y que también lindara con Cortegana.
Los 544 años de período musulmán son los más interesantes de la historia de Niebla, pues durante ese tiempo fue una ciudad de prestigio, conocida como Lebla Al- Hamra por los geógrafos árabes. Niebla y su Cora (que se corresponde casi con el actual territorio del Condado) pasan por tres importantes etapas:
En el primer período, fue tomada por Muza en el año 713. Tras su marcha, Lebla se subleva hasta que es sometida de nuevo por Abril-Azis. Bajo la dominación de los Omniadas, la ciudad sufre asaltos y saqueos por parte de los normandos (845 y 859) y rebeliones de los antiguos habitantes (los mulatos) hasta el reinado de Almanzor. Al final del califato de los Omeya, se produce una fitna o desmembración del mismo y la dinastía de los Beni-Yahya se hace con el poder de la ciudad, convirtiéndose Yahsopi en rey taifa independiente en el año 1.019. El ejército de Niebla destaca como aliado de los reinos taifas de Mértola y Silves que, junto con el de Badajoz se enfrentan al de Sevilla por el dominio de Al-garb. Pero, finalmente, la ciudad acaba rindiéndose a Al-mutadid, dejando de ser independiente al ser absorbida por el reino de Sevilla en 1051. En los períodos de paz, Lebla y Sevilla corrieron parejas en el florecimiento de las artes, la agricultura y la cerámica. En estos años nacen, San Walabonso y su hermana María (mártires y patronos de Niebla).
En una segunda etapa, las constantes luchas internas entre emires, provocan la venida de ciertas tribus del Sahara, conocidas como los almorávides. En 1091, éstos dominan todo Al-andalus y Lebla deja de depender de Al-Mutadid de Sevilla. La ciudad alcanza un alto grado de desarrollo, en el que, gracias a la tolerancia islámica, se mantiene un buen grupo de cristianos que conservan su fe y sus costumbres y las iglesias con sus obispos y cultos. La ciudad florece y llega a tener 40.000 habitantes.
En 1145, con la llegada de los almohades, que saquean la ciudad, se inicia un nuevo período. Lebla se rebela poco después contra estos invasores y, en 1154 Abu Zarcaya-Ben-Yumar, enviado por el emir almohade a pacificar Al-Garb, toma Lebla por asalto, pasa a cuchillo a todos los varones que la habían defendido y vende a las mujeres y niños como esclavos. Enterado el emir de su crueldad, lo manda llamar y encarcelar, y trata de repoblar y restaurar Lebla, restableciendo la dinastía de los Beni-Yahya. Con la batalla de las Navas de Tolosa en 1212, el poder de los almohades decae. El último rey independiente de Lebla, Aben Mahfot, se proclama rey del Algarve y fija su residencia en Lebla haciéndola capital de su reino y acuñando monedas con su nombre.
En 1262 Niebla es tomada por el rey Alfonso X el Sabio. El asedio no es fácil ni para los sitiadores ni para los sitiados, ya que, por la importancia de las defensas de la ciudad, éste duró nueve meses y medio, teniendo que rendirse por hambre. En el asedio estuvo el mismo Rey en persona, que concede a Niebla fuero Real como a Sevilla, al ser la primera ciudad que conquista. La conquista de Niebla es también un hito histórico porque es la primera vez que se usa la pólvora en España, como está recogido en las crónicas de Alfonso X el Sabio.