Medina Sidonia es una de las más antiguas poblaciones de la Baética y se atribuye su fundación a los Fenícios procedentes de Sidón, del que derivaría el nombre. Poley dice que fue distinguida con los nombres de Assido, Sidonia, Cidonia, Ciduenna o Cidueña, Asidonia y otros, asegurando después que el nombre que hoy lleva significa "ciudad de nuestro señor", dando como indicación el nombre de Medina con el que los árabes distinguían a las ciudades.

En su término se encuentra el llamado Tajo de las Figuras. En territorio Tartésico la cita Estrabón, y en el solar del actual cine Thebussem se encontraron restos de un templo dedicado a Hércules-Melkart. El nombre de Azzindum, junto con una estrella de siete puntas y un toro, figuraba en monedas libio-fenicias. Distintas estatuas togadas como Doña Blanca, situada actualmente en una de las entradas de la ciudad, hércules desafiantes, galerías que minan la ciudad como las Conducciones de Agua y Cloacas Romanas del siglo I, la Calzada, artísticas aras decoradas con guirnaldas, de tiempos del Imperio, monedas y restos de cerámica, están denunciando continuamente la existencia de la Asido Caesariana, así como el hallazgo de la "Venus de la Fecundidad", encontrada en 1972 en el Olivar de las Monjas.

Según Marcos Ramos Romero fue en la época del reino Visigodo cristiano, época de la que data la Ermita de los Santos Mártires, -y más concretamente en Suintila- cuando la actividad del cristianismo en Medina aparece más pujante con la señera figura del Qbispo asidonense Pimenio. La ciudad fue conquistada por Músá en 712, quien permitió a los cristianos practicar su religión en los extramuros, continuando así el obispado, que sería luego trasladado a Cádiz por Alfonso X el Sabio, Medina Sidonia fue capital de la Cora de su nombre durante la dominación árabe, teniendo su centro, en los últimos años en la aldea de Calsana, actual cortijo de Casinas, término de Arcos de la Frontera.

El cronista Ben Zayyán dice que Medinar, beni Asselin se encuentra en la cora de Sidonia y el geógrafo ceutí Edrisi dice que está en el camino de Algeciras. Alfonso X el Sabio reconquista la población el 22 de septiembre de 1264, pasando a ocupar la línea fronteriza contra el reino granadino, lo que hace que en algún documento medieval aparezca con la denominación "de la Frontera".En 1279, el rey Sabio concede a la Orden Militar de Santa María de España, creada por el mismo monarca en 1272, los castillos de Medina Sidonia y Alcalá, ordenándole que la fortaleza ha de llamarse "Estrella", de donde quizá venga el nombre del castillo y campos de Torre Estrella. La orden de Santa María desaparece en 1280 y Sancho IV concede a la Orden Militar de Santiago los Castillos de Medina, Alcalá y Vejer. María de Molina hace señor de Medina a Alonso I Pérez de Guzmán por 150.000 maravedís viejos, del que pasó, en 1430 y bajo el reinado de Juan II, a Luis de Guzmán, maestre de Calatrava. El mismo monarca, en 17 de lebrero de 1445, elevaba a título de ducado el gobierno de la ciudad en la persona de Juan Alonso III de Guzmán, conde de Niebla y adelantado mayor de la Frontera de Andalucía, confirmando el nombramiento como hereditario en 15 de febrero de 1460.

En 1472 recibe de Enrique IV el título de ciudad. Medina Sidonia comenzaría así a pertenecer a la casa de los Guzmán hasta la supresión de los Señoríos en el siglo XIX. El propio duque, aprovechando las continuas incursiones de piratas en Cádiz, pretendió, en 1474, devolver el obispado a Medina Sidonia, preparando el Claustro de la Iglesia Mayor para este fin. Parece ser que fue en los últimos años del siglo XVI cuando tuvo lugar el derribo del castillo (ruinas del Castillo y Alcázares) para utilizar sus materiales como elementos de construcción de la Iglesia Santa María La Mayor La Coronada, desmochándose en este tiempo la llamada Torre de Doña Blanca, en la que dice la tradición que fue enterrada doña Blanca de Borbón, mujer de don Pedro el Cruel, que murió, por mandato de su marido, a manos del ballestero Juan Pérez de Rebolledo.

Una lápida redactada por el académico Modesto La fuente, en 1859, recuerda el hecho: "En esta torre estuvo presa/ y acabó sus días a manos del ballestero/ Juan Pérez de Rebolledo, en el año 1361,/la virtuosa y desventurada reina / doña Blanca de Borbón, / esposa de don Pedro de Castilla. Conserva la ciudad tres de sus antiguas puertas; la Puerta del Sol, el Arco de Belén y el Arco de la Pastora, declarado monumento histórico artístico en 1931. El marinero José Butrón de Múgica fue el defensor de la ciudad ante la invasión francesa, que tuvo lugar desde el 2 de febrero de 1810 al 25 de agosto de 1812.

Durante el turbulento siglo XlX Medina Sidonia llegaría a ser cantón, y la languidez de su florecimiento sería el factor esencial de su decadencia. De la época visigoda -se asegura la edificación en el año 630.