La primera iglesia parroquial de San Cristóbal de La Habana, estuvo situada muy cerca de la primera plaza pública de la entonces naciente ciudad. Era un simple bohío de guano, como la mayoría de las rústicas viviendas que conformaban la Villa, con el único distintivo de una espaldaña de madera para las campanas.

Esta modesta iglesia continuó en el mismo sitio hasta que en 1550, bajo el gobierno de Gonzalo Pérez de Angulo, el cabildo acordó que se construyera una iglesia de piedra y teja. Con un presupuesto de setecientos ochenta y seis pesos de oro comenzó a edificarse la iglesia en el lugar que hoy ocupa el Museo de la Ciudad.

Cuando el 1º de julio de 1555 el pirata francés Jacques de Sores incendia y saquea la ciudad, sólo quedan en pie las paredes de la iglesia, el hospital y la casa de Juan de Rojas, uno de los vecinos más ricos de la villa. Cinco años después de la destrucción del templo, el pueblo estaba aún sin iglesia.

La intención de acometer la construcción de la obra aparece referida en el acta del cabildo del 28 de marzo de 1574. Un año después, el gobernador y el cabildo piden ayuda al Rey para edificar la sacristía, la tribuna y la torre. Pero no es hasta casi un siglo más tarde que el señor obispo Don Juan de Santos Matías, con el auxilio de las limosnas de los vecinos, reedifica y amplia la iglesia que toma el nombre de Parroquial Mayor tras el establecimiento de las parroquias del Espíritu Santo, el Cristo del Buen Viaje y el Santo Ángel Custodio.

Otro desastre provoca el resquebrajamiento de la Parroquial, esta vez el incendio del navío El invencible que deja a la edificación totalmente en ruinas, por lo que años después se hizo necesario su derribo definitivo. En 1777, la Parroquial Mayor pasó a la iglesia de los Padres Jesuitas, proclamada Catedral de La Habana a finales de 1793.