Medina Sidonia tiene el honor de ser una de las primeras poblaciones de la Baética y según los datos historiográficos, fueron los fenicios provenientes de Sidón los que la fundaron. El nombre de Medina Sidonia proviene de que el origen de los fenicios que desembarcaron por primera vez en sus costas eran oriundos de ese puerto de oriente próximo.

También la presencia de los Tartesos se haya constatada por los restos que han aparecido de esta tribu íbera. De hecho se ha encontrado inclusive las ruinas de un templo que estaba bajo la advocación de Hércules-Melkart. El término Azzindum, nombre con el cual se conoció Medina Sidonia aparecía reflejado en unas monedas libio – fenicias junto con una estrella de siete puntas y un toro.
Los romanos también dejaron vestigios de su paso con estatuas togadas como Doña blanca, figuras de Hércules desafiante y conducciones de agua y cloacas. En aquella época los romanos llamaron a Medina Sidonia con el topónimo de Asido Cesariana.

 Uno de los monumentos de mayor relevancia de la época visigotica es la Ermita de los Santos Mártires que nos habla de la actividad cristiana en la localidad.
En el año 712 el caudillo musulmán Musa la conquista para los árabes y permite que los cristianos sigan manteniendo su culto religioso fuera de los muros de la ciudad. Esta localidad durante la ocupación musulmana fuer la capital de la cora homónima siendo su centro la aldea de Calsana que en la actualidad es el cortijo de Casinas, dentro del término municipal de Arcos de la Frontera.

En el año 1279 Alfonso X el Sabio da la propiedad de los castillos que se encontraban en lo que ahora es Medina Sidonia a la Orden Militar de Santa María de España, llamando Estrella a la fortaleza de Medina Sidonia. Desaparecida la Orden Militar, con el advenimiento del rey Sancho IV la propiedad del castillo pasa a manos de la Orden Militar de Santiago.
En 1.472 Medina Sidonia pasa a pertenecer al señorío de los Guzmán hasta el siglo XIX en el cual este señorío se suprime. La familia de los Guzmán decide la construcción de la iglesia de Santa María para lo cual derriba el castillo, y es en el solar que resulta dónde se lleva a cabo la construcción.
Durante el siglo XIX Medina Sidonia adquirió la entidad política y geográfica de cantón y a partir de ese momento comienza una suave y progresiva decadencia.