Tras la conquista de la ciudad en 1230 por parte del Reino de León, se convierte la mezquita de Ibn Marwan (en la Alcazaba) en templo cristiano. Este templo fue la primitiva catedral de Badajoz, denominada Catedral de Santa María del Castillo. Junto con la reconquista, la ciudad se convirtió en sede episcopal, y el primer obispo, Fray Pedro Pérez decide iniciar la construcción de una nueva catedral en 1232. Este edificio fue consagrado por Fray Lorenzo Suárez entre 1273 y 1280.

    En el aspecto exterior de la Catedral de Badajoz coexisten distintos estilos como los que indican los elementos góticos, renacentistas y barrocos. La Catedral es de aspecto austero y sencillo, comparada con otras catedrales coetáneas (León, Burgos, Toledo). Motivos de esto fueron: la situación fronteriza de la ciudad, sometida a continuas guerras y destrucciones; la construcción de la Catedral fuera del recinto protector de la Alcazaba; y la escasez económica de la ciudad en la época. Por esto encontramos una construcción robusta, con almenas y merlones, escasez de vanos al exterior, etc.

       El cuerpo de la Iglesia se construye entre la segunda mitad del siglo XIII y finales del XIV. Varios factores explican el largo plazo de construcción:  pobreza económica del cabildo, población de la ciudad relativamente escasa y su penuria económica, inexistencia de una burguesía rica, la sucesión en la sede episcopal que podría retardar los planes e incluso cambiarlos, la ya mencionada inestabilidad económica y social provocada por el proceso repoblador y las guerras civiles castellanas, que, casi sin interrupción, se extienden desde el último cuarto de siglo XIII al último cuarto del siglo XV.

     Se establecen una serie de fases en la construcción del complejo catedralicio:

1) Segunda mitad del siglo XIII hasta el último cuarto del siglo XIV: Durante este período se proyectaría la planta de cruz latina de la Iglesia con tres naves y tres ábsides poligonales y un crucero que no llegó a cubrirse. La nave central y la del crucero son de mayor altura que las naves laterales para poder permitir la iluminación del interior por medio de ventanales. Durante esta fase sólo se levantó la cabecera y el crucero. También se levanta un claustro situado en el mismo solar que el actual, pero de dimensiones más reducidas. Los ábsides se cubren con bóveda de crucería simple mientras el primer tramo de la nave central lo hace con bóveda de doble tracería.

2) Último cuarto del siglo XIV y primera mitad del siglo XV: Se cubre el crucero y se levantan dos nuevos tramos de las naves, cubriéndose todos ellos con bóvedas de crucería simple. Se fija además la colocación del resto de los pilares de las naves.

3) Segunda mitad del siglo XV: Se construyen los tres últimos tramos de las naves con las mismas características de cubierta y se proyectan dos torres a los pies del edificio, de las que sólo se levantará una, la del lado noroeste.

4) Siglos XVI y XVII, hasta 1662: Se añaden las dos naves de capillas, se construye el nuevo claustro, se remata la actual torre y se construyen las tres portadas.

5) Último tercio del siglo XVII y primer cuarto del XVIII: Reforma de la cabecera, en la cual desaparecen los ábsides poligonales que se sustituyen por testeros planos. Construcción de la sacristía, la sala capitular y otras dependencias auxiliares.