Aunque se desconoce con exactitud la fecha en la que fue fundado, la bibliografía sobre este templo lo sitúa en el siglo XVII, aunque existen otros documentos que demuestran que su construcción fue mucho más antigua, pues a finales del siglo XVI se cita en un testamento al Convento de Santa Ana como lugar que ofrecía misas y enterramientos.
Un claro exponente de la presencia de las Órdenes Mendicantes es el propio convento que nos proponemos a describir y el Convento de Ntra. Sra. Reina de los Ángeles, asentados ambos en los límites de la ciudad, hoy día rodeados de núcleo poblacional que ha ido creciendo con el paso de los siglos.
Sede de la Iglesia de la Misericordia-Santa María la Coronada, la Iglesia y convento de la Victoria estaba situado a las afueras de la ciudad aprovechando las vías de comunicación por el norte que procedían de Ubrique y Cortes de la Frontera, lo que conllevaba un crecimiento urbano en torno al mismo, potenciándose entorno a él toda una serie de inmuebles como la Pescadería, la Carnicería o los Corrales de Santa Ana, actuando como zona comercial de la villa.
A mediados del siglo XVIII, se realizan una serie de obras y añadidos que afectaron en cierta medida a la configuración del edificio. Por aquel entonces, la iglesia contaba con una sola nave, sin campanario, un claustro adosado al muro de la epístola y una huerta situada en la parte posterior y lateral. Todo ello garantizaba una vida en comunidad, dotando las dependencias para el pleno funcionamiento de la clausura, dotándola de cocina, lavadero, despensas para guardar grano, cuadras para guardar ganado, y toda una serie de estancias que garantizaban la subsistencia de toda la comunidad.
En el siglo XX, durante la ocupación francesa de la ciudad, pocos son los datos que se tienen acerca de las transformaciones y destrozos que se hicieron en el templo dado que tenían por costumbre ocupar los conventos y utilizarlos como cuarteles para las tropas.
La iglesia, en la actualidad consta de dos naves y aunque hoy en día muy reformadas, presenta a su vez un campanario, una portada muy simple y un pintoresco patio. Adoptando el nombre actual en honor a la patrona de Málaga.