Se levantó a finales del siglo XVII, con una superficie de 647 m², y estuvo habitada por dos congregaciones religiosas distintas: los hospitalarios y los victorios, siendo de estos últimos de quienes toma el nombre la iglesia. Los victorios llegan a Medina Sidonia en 1579, ubicándose en un principio en la antigua ermita de San Sebastián, actual iglesia de San Juan de Dios; de ahí su vinculación con ella.

La iglesia resulta incendiada en 1873, abriéndose de nuevo al culto en 1875.

En el siglo XIX se convierte en escuela y viviendas para maestros.

La planta se compone de tres naves, con cúpula central sobre pechinas frente al altar mayor y nave central cubierta por bóveda de cañón y arcos fajones sustentados por gruesos pilares.

El primer piso se divide por tribunas y el coro.

Es importante destacar las imágenes del retablo principal, con la Virgen de la Victoria, San José —obra de Juan Martínez Montañés—, San Antonio y San Fernando.

En los demás altares se pueden ver imágenes que procesionan en la Semana Santa Asidonense, como María Santísima del Mayor Dolor, preciosa talla atribuida al imaginero Diego Roldán. Es una talla de candelero, de vestir, con expresión de dolor, con su mirada hacia el cielo. Otras tallas son Ntro. Padre Jesús de la Columna (autoría anónima del siglo XVI), Stmo. Cristo de la Sangre, imagen atribuida a los talleres de Roldán, y San Juan Evangelista que data del 1698. Al igual que las demás iglesias de esta ciudad, esta sufrió la desamortización de aquella época, perdiendo así parte de su riqueza.^[1]​

• Área de Promoción de la ciudad del Exmo. Ayuntamiento de Medina-Sidonia. Jornadas de Puertas Abiertas. Diciembre de 2007.
• El contenido de este artículo incorpora material de una entrada de Cadizpedia, publicada en castellano bajo la licencia de documentación libre de GNU.