Su origen arranca de la reconquista de la ciudad por los Reyes Católicos, que se rindió el 18 de agosto de 1487. En este lugar se encontraba el campamento del rey don Fernando y sobre él se levantó una pequeña ermita para custodiar a una imagen de la Virgen con el Niño, que según la tradición, había enviado a los Reyes el Emperador Maximiliano de Austria; ella fue el aliento espiritual de la larga campaña y se le atribuyó el triunfo sobre la Málaga Musulmana, por lo que se dio el sobrenombre de Virgen de la Victoria, convirtiéndose en Patrona de Málaga.En 1492, los frailes Mínimos de San Francisco de Paula, que habían reconfortado moralmente a los reyes durante el cerco, fueron autorizados a fundar y pidieron la Real Capilla de Nuestra Señora de la Victoria, que les fue concedida, fundando en 1493 la casa matriz de la orden en España.
Junto a la ermita, se fue edificando el establecimiento conventual (se puede observar el patio cuadrangular en el actual hospital allí situado), e inmediatamente una nueva iglesia que fue consagrada en 1518; debía tener una sola cubierta con armadura de madera con tirantes, a la que se abrían las capillas laterales.
La iglesia actual, con su camarín y torre, data de los últimos años del siglo XVII y ocupa el solar de la primitiva. En 1691, un procer malagueño, el Conde de Buenavista, ofreció ampliarla y repararla a su costa, para construirse una capilla-enterramiento, pero al reconocerla los alarifes informaron de que el estado de ruina del templo no resistiría la ampliación, por lo que fue derribado en 1693, levantándose un nuevo templo. El conde costeó la obra de la iglesia de la que conservaron sus cimientos y levantó además el pórtico, el campanario, la sacristía y antesacristía, el camarín un panteón privado y otro para la comunidad. El Patronato de las capillas debía mantenerse a pesar de las reformas, conservando los Córdoba el de la capilla Mayor con derecho a enterramiento en su bóveda, por lo que el Conde no pudo ocuparla y construyó la cripta inferior. La obra se inauguró en 1700.
El conde contó con dos colaboradores extraordinarios, Fray Alonso de Berlanga, erudito fraile mínimo, conocedor extraordinario de los textos sagrados, que pudo intervenir en el proyecto, y un gran arquitecto y decorador, Felipe de Unzurrúnzaga.