La mayoría de los historiadores están de acuerdo en que la iglesia de San Sebastián Mártir del Antiguo tiene más de mil años. Además, en el año 1014 (existen opiniones divergentes sobre la fecha exacta del documento) el rey Sancho Garcés III de Pamplona ya había cedido este templo al Monasterio de Leyre, al que consideraba, ya entonces, "antiguo".
En la primera guerra carlista se destruyó la Iglesia del Antiguo en 1836, que también fue utilizada como iglesia conventual de las MM. Dominicas, convento fundado por los frailes de San Telmo en el siglo XVI.
En 1887, cuando la reina María Cristina se interesó por la zona donde estaba ubicada esta iglesia, el ayuntamiento se ofreció a construir un palacio de verano como regalo.
El 11 de julio de 1888 el alcalde de San Sebastián, Gil Larrauri, se dirigió al obispo de la diócesis pidiendo permiso para trasladar la iglesia a la calle Matía con el fin de que en su lugar pudiera construirse lo que sería el Palacio de Miramar. El 24 de septiembre de 1888 se colocó la primera piedra de la nueva iglesia, ahora visible. María Cristina de Borbón y su hijo el rey Alfonso XIII estuvieron presentes en la ceremonia de bendición del nuevo edificio del 7 de septiembre de 1889.
En 1889 se reconstruyó y se le añadió una torre-campanario para aprovechar los materiales sobrantes del derribo de la cercana ermita de Loreto. Esta obra la realizó el arquitecto municipal José Goicoa.
En los años 60 del siglo XX, con un aforo de unas 500 personas en un barrio de 2000 familias, se plantea la ampliación de la iglesia. Sobre un planteamiento de capacidad para 1000 personas, viviendas para los clérigos y locales pastorales varios, se encarga la redacción del proyecto de ampliación al arquitecto Pablo Zabalo (1893-1961), que falleció al poco de comenzar el encargo, y siendo continuado y finalizado por Andrés Barrenetxea. En noviembre de 1961 se inicia la reforma de la iglesia vieja y se inician las obras del nuevo templo. La nueva iglesia se inauguró el 1 de mayo de 1964.
