Tal como hoy se encuentra la iglesia tiene tres naves más dos capillas entre contrafuertes, atrio y coro elevado a los pies y un amplio presbiterio trebolado, que pertenece a la ampliación de 1767. La nave central, cubierta con bóveda de medio cañón con yeserías y lunetos que se amplían con molduras para disponer pinturas del siglo XVIII rodeadas por baquetones y rocalla, se separa de las laterales por pilares con pilastras corintias que voltean arcos de medio punto, reforzándose sus pedestales con mármoles polícromos. La unión de las naves laterales con el presbiterio se efectúa por sólidos arcos de medio punto sesgados, decorados con relieves de estuco, en molduras rococó que representan a la Virtudes. Crucero no existe, sino una nave transversal que forma el cuerpo trebolado con la capilla mayor y es la zona más decorada. En el centro se halla una bellísima cúpula con linterna decorada con medallones, lazadas y rocallas integrando pinturas y se corona con esbelto cupulín también abierto; los brazos laterales rematados en forma absidal se cubren con bóveda de cascarón decorados con más secillez. La capilla mayor queda ligeramente elevada y se cubre con el mismo tipo de bóveda, pero con mayor riqueza decorativa.

Fue fundada por los Reyes Católicos en virtud del voto, que tenían hecho antes de la Reconquista, de establecer en Málaga el culto a los Santos Mártires Ciríaco y Paula. Se levantó nueva desde los cimientos en 1491, dejando la reina en su testamento una considerable cantidad para la obra, que se erigió en 1505 como parroquia. La primitiva iglesia era mucho más pequeña,cubierta con armadura de madera, oculta hoy bajo la bóveda barroca, sufriendo diversas reformas, pero las ruinas que le causaron terremotos, incendios e inundaciones, hicieron preciso una restauración y ampliación, que se inició en 1767, acabándose diez años más tarde y con una decoración rococó muy profusa, que quedó convertida en una de las iglesias más interesantes de la ciudad.