Lisboa es sede de una diócesis desde el siglo IV d. C. Después del periodo de dominación visigoda, la ciudad fue conquistada por los musulmanes y se mantuvo bajo control árabe desde el siglo VIII hasta el siglo XII cuando en 1147 fue conquistada por Alfonso I de Portugal. En ese periodo se permitía a los cristianos vivir en Lisboa y los alrededores y mantenmer sus costumbres y fe, Lisboa contaba con un obispo mozárabe.

Tras la conquista se nombró obispo de Lisboa al inglés Gilberto de Hastings que restauró la diócesis lisboetense. En 1147 comienzan las obras del primer edificio que finalizarían en 1247. Se estima que se levantó sobre la antigua mezquita de la ciudad aunque falta documentacuión fehaciente para afirmarlo,[1]​ Entre las hipótesis más plausibles, podemos destacar la que defiende el Abad de Castro en su obra O Templo da Invocación de Santa María en la que menciona que pudo haber existido en el mismo sitio un templo pagano consagrado al Dios Sol, en época de Paulo de Olisipo romana (Apolo-Sol). Esto ha sido respaldado por el hallazgo de inscripciones romanas en la parte subterránea de la catedral descubierta tras el terremoto; una serpiente tallada en el cimborrio que puede simbolizar a Phiton (la que mató al dios); también Emílio Hübner (“Notícias Arqueológicas de Portugal”) defiende la existencia de un templo pagano desde tiempos de Décimo Junio Bruto, hipótesis que se apoya en la certeza de la existencia del foro de Paulo de Olisipo en el espacio frente a la fachada principal de la Sé, con una basílica o un templo entre sus edificios. También es de tener en cuenta la conversión al Cristianismo de la ciudad en época del obispo Potamio, y la posibilidad de que este o sucesores, hubiesen transformado el templo pagano en un templo del Paleocristiano de planta central. Esto se apoya en la existencia de una serie de piedras labradas reutilizadas en la actual Sede. Tras la invasión por parte de los pueblos islámicos, algunos autores defienden que el edificio existente hubiese sido aprovechado para uso como mezquita, sin introducir reformas relevantes. Lo más probable es que Afonso Henriques mandara reconstruir la Sede sobre un edificio que no sería árabe. De este modo, lo que se produciría sería la reforma y ampliación de un templo Paleocristiano surgido en época constanina, utilizado bajo dominio suevo y visigodo, y posiblemente también bajo dominio islámico.

El edificio original era de estilo Románico tardío, conformado por tres naves con triforio, crucero volado y crucero con tres capillas. Muy similar al de la Catedral Vieja de Coímbra siguiendo los modelos normandos, el proyecto fue dirigido por Mestre Roberto de Lisboa, probablemente de origen normando, quien trabajó en la construcción de la Catedral de Coimbra, Lisboa y el Monasterio de Santa Cruz de Coimbra.[2]​ Afonso Henriques trae desde el Algarve las reliquias de San Vicente de Huesca qiue sería el patrón de la ciudad, y quedan depositadas en la catedral. A fina del les del siglo XIII Dionisio I de Portugal construyó un convento gótico y su sucesor, Alfonso IV, convirtió la capilla principal en panteón real para sí y su familia. Las influencias normandas estarían relacionadas con la estrecha relación que durante la Segunda cruzada entablaron los portugueses con los ingleses que dio lugar al nombramiento de Gilberto de Hastings como obispo de Lisboa.

En 1498, la reina Leonor fundó la Misericórdia de Lisboa en una de las capillas del convento de la catedral. La Misericórdia es una institución caritativa católica que luego se expandió por otras ciudades y que fue muy importante en Portugal y en sus colonias.

Entre los siglos XIII y XIV se construyó el claustro gótico, una de las principales obras arquitectónicas del reinado de Dionisio I de Portugal.[3]​ Su sucesor, Afonso IV, modificó la parte trasera de la iglesia románica, mandando construir un ábside con girola de estilo gótico para ser utilizado como panteón familiar.[3]​[4]​ La voluntad del rey se quedó expresada en su testamento, fechado en 1345, en el que dice que

A pesar de la prohibición medieval de enterrar a los laicos en el presbiterio, se hizo una excepción para el rey Afonso IV por su heroica actuación en la Batalla del Salado de 1340.[5]​ El nuevo crucero comenzó a construirse en la primera mitad del siglo XIV finalizando a principios del siglo XV, durante el reinado de Juan I de Portugal, cuando las tumbas de Alfonso IV y su esposa, Beatriz de Castilla, fueron trasladados a la capilla mayor.[4]​ La creación de un deambulatorio con una serie de capillas en el ábside fue una obra de modernización de la Catedral que la hizo más apta para recibir a los peregrinos que venían a ver las reliquias de San Vicente.[5]​[4]​ En el siglo XIV, Lisboa y la Catedral se vieron afectadas por varios terremotos. Un fuerte terremoto a principios del siglo XV provocó cambios en las obras, en esa época es posible que los arcos que conectaban el corredor del deambulatorio con el presbiterio estuvieran cerrados.[5]​[4]​

A lo largo de los siglos, la Catedral fue decorada con diversos monumentos y altares, la mayoría de los cuales se han perdido o se encuentran dispersos por otras propiedades. El presbiterio albergaba el sepulcro con las reliquias de San Vicente, que fue decorado hacia 1470 con un gran retablo pintado -el llamado Paneles de San Vicente de Lisboa- de autoría atribuida a Nuno Gonçalves, pintor real de Alfonso V de Portugal.[6]​ Los paneles, obra maestra de la pintura portuguesa del XV, fueron desmontados en 1614[5]​ y hoy se encuentran, junto con otras pinturas de la Catedral asociadas a São Vicente, en el Museo Nacional de Arte Antiguo de Lisboa.[6]​

En 1498, la reina Leonor de Viseo fundó la Hermandad de Invocación a Nuestra Señora de la Merced en la Capilla de Pedra Solta en el claustro de la Catedral.[5]​ La Hermandad finalmente dio origen a la Santa Casa de la Misericordia de Lisboa, institución caritativa católica que se extendió a otras ciudades del reino y colonias.[7]​

A mediados del siglo XVII se construyó una sacristía de estilo manierista junto a la fachada sur.[3]​[5]​ En el siglo XVIII se reforma la capilla gótica la cabecera en estilo barroco.[3]​ El edificio fue afectado por el terremoto de 1755, el cual destruyó la Capilla del Santísimo Sacramento, la torre sur y la decoración del presbiterio, incluidas las tumbas reales, y el claustro.[5]​[8]​ Así mismo el Cimborrio se derrumbó parcialmente dañando parte de las bóvedas de las naves que fueron reconstruidas en madera.[8]​[9]​

En las décadas siguientes, la Catedral pasó por varias reformas y una campaña de redecoración. Así, entre 1761 y 1785, se reconstruyó la Capilla del Santísimo.[5]​ Entre 1769 y 1771, Reinaldo Manuel dos Santos coordinó importantes obras de restauración de la torre sur de la fachada principal, construyó el techo de madera de la nave y remodelación del presbiterio, incluida la pintura de la bóveda y la decoración en estuco de Félix da Costa.[5]​ Las naves se cubrieron con madera pintada decoración y estuco y el nuevo revestimiento de madera de la nave central se dotó de óculo que dejaba pasar la luz.[9]​

En el presbiterio se reconstruyó el panteón real en 1781 depositando los restos de mortales de los reyes de Portugal en nuevos sarcófagos tallados por Joaquim Machado de Castro y entre 1787 y 1788 se realizaron nuevas tribunas reales construidas por António Ângelo.[5]​ Entre 1785 y 1786 Joaquim António Peres Fontanes construyó dos nuevos órganos en el presbiterio cuyas cajas fueron talladas por António Ângelo.[5]​