El Cerro del Castillo y el Cerro de las Madres, en relación a los cuales se organizará el núcleo urbano principal de la localidad, se encuentran habitados desde la Protohistoria, y el primero de ellos fue germen de una entidad urbana y cívica.
Este territorio hubo de ser ya conocido y frecuentado desde las primeras etapas de la Prehistoria.
Este ámbito espacial está enmarcado en la zona más meridional de la Península donde hay importantes evidencias de la ocupación de grupos de cazadores-recolectores durante el Pleistoceno, y que se conforman como una de las vías del primer poblamiento de Europa desde África, a través del Estrecho de Gibraltar.
La continuidad y características de este poblamiento durante el Pleistoceno final e inicios del Holoceno adolece igualmente de la falta de investigación.
Los abrigos con arte rupestre en Benalup-Tarifa son testimonios cercanos de dicha continuidad.
Igualmente se desconoce cómo fueron los asentamientos de los grupos neolíticos con una economía ya productora y su evolución posterior.
Sin embargo se conservan interesantes testimonios de estas comunidades en el arte de los abrigos y en los conjuntos dolménicos de la comarca de la Janda.
Sobre la base de un poblamiento característico del Bronce Final (yacimientos de El Berrueco y el Cerro de las Madres) hubo de constituirse en el solar de la actual Medina Sidonia una primera entidad urbana, Asido, expresión de una formación social propia de la Edad del Hierro, coprotagonista, a la par que Gadir y Asta, del proceso histórico de una región que se extendía desde las inmediaciones del Estrecho de Gibraltar hasta la desembocadura del Guadalquivir.
Poco se sabe de esta etapa de la historia de Asido, ni de su territorio, ni de la ocupación y poblamiento del mismo.
Aunque se quiere vincular el origen de Asido a la colonización fenicia, hay pocos argumentos sólidos.
Se funda particularmente esta hipótesis en el topónimo y su semejanza con la denominación de Sidón, ignorando que tal prefijo As-/Ast resulta habitual en el poblamiento coetáneo del territorio andaluz, como por ejemplo en la cercana Asta, o en Astigis.
No es ajena sin embargo esta incipiente sociedad asidonense al influjo del cercano espacio semita y sus actividades de intercambio, alcanzando sus productos al núcleo y al territorio de la misma.
Las fuentes literarias clásicas alusivas a Asido son parcas.
Se ignora desde esta perspectiva su devenir histórico durante la presencia Bárquida en el sur peninsular, pues ningún autor clásico se detiene en ello, sin embargo algunos de los yacimientos catalogados muestran una cultura material relacionada con este período, aunque a simple vista de escasa entidad.
En cambio acuñó moneda con leyenda libiofenicia, lo cual conduce nuevamente a la existencia de un rol histórico significativo de la localidad.
Cabe suponer para esta etapa la existencia de una explotación territorial articulada desde Asido, así como la presencia de elementos propios de la vigilancia, el control y la defensa del territorio.
La primera fase de la presencia romana en el territorio asidonense, la etapa republicana, puede caracterizarse, a la etapa púnica: escaso conocimiento; indicios de ocupación en determinados enclaves rurales; asentamientos posiblemente vinculados al control del territorio y su circulación.
La información procedente de las excavaciones urbanas puede suplir en este caso las carencias manifestadas en el conocimiento del territorio.
Es Plinio una de las fuentes que informa del carácter colonial de Asido Caesarin.
Sin embargo, no hay acuerdo en otorgar el protagonismo de la creación de la colonia asidonense a César o Augusto.
Además de los recientes hallazgos monumentales en el Cerro del Castillo, no cabe duda de la actuación sobre el territorio de la ciudad, que hubo de conocer parcelación y asentamientos de colonos en sus tierras más fértiles generando yacimientos arqueológicos vinculados con la explotación agrícola, algunos de los cuales son conocidos, como por ejemplo el denominado Cordones Sur.
El nuevo papel central en este espacio que adquiere Asido, por delante de Asta y Gades alcanza su mayor expresión durante el episodio de la constitución de la provincia bizantina de Spania.
Assidone la denomina la fuente itineraria tardía del Ravennate.
En estas fechas la localidad será un bastión bizantino.
Nada relacionado con este período se documenta en los asentamientos conocidos hasta la fecha en el término.
Esta condición de fortaleza bizantina acaba con los asaltos por parte de las tropas de Leovigildo.
La ciudad visigoda ha dejado también indicios escultóricos relacionados con una nueva edilicia, tanto en el casco histórico como en la Ermita de los Santos Mártires, de la cual destaca asimismo el epígrafe fundacional.
Poca información se halla en los bienes estudiados que puedan remitir a esta cultura y período, salvo la necrópolis ubicada en la denominada: Mesas de Algar.
La islamización ulterior no sólo no acabó con la posición preferente de la ciudad, sino que le mantuvo como cabeza de la circunscripción territorial, la cora, de Medina Asidona, siendo ahora lógicamente cuando adquiere la ciudad el epíteto que conserva en la actualidad.
Diversas son las alquerías identificadas en su territorio indicadoras de una intensa ocupación y explotación andalusí de su espacio agrario.
Ejemplo de su esplendor en esta etapa es la construcción de la fortaleza defensiva enclavada en la cota superior de la ciudad, de la que se conservan restos de sus muros y puertas fuertes, como la denominada Puerta de la Pastora.
La ocupación cristiana de Medina Sidonia se produce en tiempos de Fernando III, en 1249, volviendo a caer bajo el control musulmán hasta 1267, cuando es definitivamente tomada por Alfonso X.
Fruto de estos acontecimientos fue el habitual proceso de reparto de tierras entre los conquistadores y nuevos pobladores.
Seguidamente se produjo un nuevo proceso de colonización agraria vinculado a estos hechos históricos que suponen tanto la continuidad de muchas alquerías islámicas como la creación de nuevas cortijadas vinculadas con la explotación del agro.
Desde los inicios de la Medina cristiana, la ciudad constituyó la sede de renombradas órdenes militares, como la Orden de Santiago y la Orden de Santa María de España.
Recibió durante años favores reales de Alfonso X El Sabio, así como de los monarcas que le sucedieron, como lo demuestra la magnífica colección diplomática que se conserva en su Archivo Histórico Municipal desde el siglo XIII.
La villa sirvió y acogió a los Duques de Medina Sidonia desde el año 1440, cuando fue entregada a D.
Juan de Guzmán, tercer Conde de Niebla y primer Duque de Medina Sidonia, recibiendo el título de Ciudad en 1472, de manos del Rey Enrique IV.
Durante buena parte de la Edad Moderna la población fue nuevamente cabeza política de la comarca, integrada en el ducado de Medina Sidonia, que continuará hasta las Cortes de Cádiz, aunque es en realidad en 1837 cuando los señoríos son abolidos definitivamente.
De esta época perviven restos de construcciones señoriales, así como varios tramos del recinto amurallado cristiano, en el que se conservan tres de las cuatro puertas originales: el antes mencionado Arco de la Pastora, El Arco de Belén y la Puerta del Sol.
De los siglos posteriores nos han llegado edificios públicos, así como una rica arquitectura religiosa, cuyo máximo exponente se refleja en la Iglesia de Santa María La Mayor La Coronada.
En 2001 Medina Sidonia fue declarada Bien de Interés Cultural en la categoría de Casco Histórico.
La tradicional ocupación del espacio agrícola asidonense se atestigua en la profusión de bienes catalogados que indican su permanencia en la Edad Moderna, a los cuales se deben añadir otros elementos del paisaje, como los dos puentes, relacionados con las principales vías de comunicación que atravesaron el municipio.
Los acontecimientos más destacados durante la Época Contemporánea en la localidad fueron: la ocupación de la misma por las tropas napoleónicas entre 1810 y 1812 y el establecimiento de su cuartel general en la llamada Villa Vieja, en el Cerro del Castillo; la construcción en 1837 de sendos edificios públicos en el Barrio de Santiago, el matadero y la alhóndiga, la creación del nuevo cementerio, el mercado de abasto y el Teatro; y la declaración en 1873 del Cantón Independiente de Medina Sidonia.