La iglesia de San Sebastián se asienta sobre los restos de una ermita. Los únicos vestigios de ésta son un muro y los contrafuertes de la cabecera, visibles desde la calle de la Palma esquina con calle San José. Se sabe que al menos desde la década de los 30 del siglo XVI ya habría actividad funeraria.[3] Se sabe que la iglesia fue consagrada en 1592, como reza la columna fundacional situada en el atrio del templo, junto a la portada de las Novias, siendo obispo de Cádiz, Antonio Zapata.
La iglesia se empezó a construir en estilo gótico, que se observa en la cabecera, la cubierta del presbiterio y la capilla bautismal a los pies de la iglesia, presentando ambas arcos apuntados y bóveda de crucería. El estilo predominante en el edificio es el renacentista, con planta de salón separada en tres naves por columnas toscanas y amplios arcos de medio punto que aligeran la tensión longitudinal del conjunto. Las naves son de 39 metros de largo y 13 metros de ancho. La cubierta de la nave principal es de bóveda de cañón. Otras capillas, como la sacramental, fueron construidas en el siglo XVIII en estilo barroco, cubiertas con cúpula.
La portada principal que da a la calle Ancha, llamada "portada de las Novias" es de mediados del siglo XVI. Se le considera uno de los pocos exponentes del plateresco en la provincia.[4] En la parte superior figura la imagen de Dios Padre en majestad. También hay restos de ángeles y santos, además de algún elemento de una policromía anterior, pero muy deteriorados.
La iglesia en su conjunto está orientada ligeramente en dirección oeste-este, y está situada en el punto más alto del núcleo urbano de Puerto Real. Su torre es mozárabe, probablemente de origen defensivo, con cuatro campanas. Es una torre bastante sencilla con una pirámide con azulejos en la cima.
El 3 de marzo de 1754 sufrió un incendio que destruyó buena parte del templo. Aún así con la bonanza de la villa en aquel momento se pudo reconstruir la iglesia en su totalidad.
Sufrió un incendio a principio de la guerra civil española, siendo restaurada por Germán de Falla (hermano del músico Manuel de Falla) y reabierta al culto 10 años después, en 1946.[5]