La iglesia de San Francisco de Paula, situada en la calle Paula esquina a San Isidro, hubo de erigirse en el año 1667, como última voluntad recogida en el testamento del sacerdote Nicolás Estévez Borges. Este dispuso la construcción de una ermita bajo este título y con el remanente de sus bienes edificaron el hospital de mujeres añadido a la iglesia.
Contaron con el respaldo del obispo Juan de Santo Matías para la construcción del templo y del hospicio, el cual tenía al principio cuatro camas para el restablecimiento de mujeres pobres y desvalidas. En 1730 en la ciudad azotó un gran temporal que destruyó la primitiva iglesia, que al parecer no era muy resistente. Poco tiempo después comenzaron a construir un nuevo templo, pero no fue concluido hasta 1745, con el impulso del obispo Lazo de la Vega.

En su fachada principal ubicaron tres esculturas, una de San Francisco de Paula, otra de San Pedro y una de San Pablo. Además, restauraron la enfermería y añadieron nuevas piezas. Las puertas del hospital y la iglesia ya estaban cerradas en 1907 y el edificio fue vendido a una empresa portuaria.
A partir de ese momento la obra fue sometida a un total abandono, sobre todo el hospital. Al final este fue demolido, por considerar que no tenía valor arquitectónico pero pudieron salvar la iglesia de este triste destino, gracias al esfuerzo incesante del entonces historiador de la ciudad, Emilio Roig.
La Junta Nacional de Arqueología y Etnología había logrado que se aprobara por decreto presidencial la Declaración de Monumentos Nacionales en 1944, por lo que inmediatamente Roig solicitó a Fernando Ortiz, presidente de dicha junta, que la Iglesia de Paula fuera declarada Monumento Nacional y así se aprobó. De esa manera la alcaldía municipal denegó la decisión de demoler la iglesia, no obstante, fue utilizada como almacén, lo que le provocó un gran deterioro, hasta que en 1946 fue restaurada por el arquitecto Félix Cavarrocas.
A partir de este momento el lugar fue utilizado para diferentes fines. Entre 1951 y 1956 se instaló el Instituto de Investigaciones Folklóricas. Años más tarde fue ocupada por el Centro de la Música hasta que ceden este espacio a la Oficina del Historiador en1996.
Durante 1996 y 1997 realizaron excavaciones arqueológicas que arrojaron datos sobre la costumbre de prestar servicios funerarios en el templo. Se comprobó que allí enterraron personas de ambos sexos, de diversas edades y con baja condición social.
La iglesia se volvió a restaurar a partir de 1998. Se tuvo en cuenta el tratamiento de los muros, fachada y cúpula. También recuperaron la cruz de hierro en su cima así como tres campanas que estaban instaladas en la antigüedad.
En la actualidad, al atravesar la Alameda de Paula, paseo que a principios del siglo XIX era punto de reunión de los habaneros, la imagen es diferente. En el 2000, tanto la iglesia como la Alameda estaban renovadas gracias a la Oficina del Historiador de la Ciudad y al apoyo financiero de la Agencia Española de Cooperación Internacional. Esta labor formó parte del plan de rehabilitación de la Avenida del Puerto desde la Plaza de San Francisco, hasta la transformación de los Almacenes de San José en un centro cultural.
La Iglesia de San Francisco de Paula, fue reformada en una Sala de Conciertos. Otro valioso aporte de su restauración lo constituyó la recuperación del órgano de la iglesia, instrumento original construido en Francia entre 1845 y 1855, fiel testigo de parte de la historia musical cubana.