La première église fut érigée, dit-on, au VIIe siècle sur le rocher d'Aaron en l'honneur de St-Malo. Elle fut incendiée par les soldats de Charlemagne en 811 et relevée en 816. L'évêque Châtillon en fit sa cathédrale au XIIe siècle. L'édifice actuel est construit en granit.
La façade ouest comprend trois édifices à toitures séparées, correspondant à la nef et aux deux bas-côtés.
La partie centrale, de style pseudo-grec date de 1772-1773. Elle est percée d'une porte en plein cintre flanquée de deux pilastres. Une grande fenêtre cintrée surmonte la porte. Un fronton triangulaire couronne le tout. L'évêque ne franchissait cette porte que le jour de son entrée solennelle et de ses funérailles.
L'aile nord, construite de 1593 à 1607 et de style Renaissance. Elle est percée de quatre ouvertures superposées : une porte, une fenêtre, un oeil-de-boeuf et une gerbière. L'aile sud est semblable à l'aile nord, quoique moins et plus récente.
Le collatéral de la nef est percé de trois fenêtres correspondant aux trois chapelles du bas-côté. La haute nef du choeur est percée de quatre fenêtres en arc brisé, flanquées de colonnettes.

Le collatéral sud possède une voute sur croisée d'ogives.

Le choeur (fin XIIIe s.ou début XIVe) se distingue du reste de l'édifice par son élégance et sa légéreté. Il atteint une hauteur de 28 mètres et comprend quatre travées. Il possède une triple verrière qui occupe toute sa largeur.

La cathédrale fut transformée en magasin au moment de la Révolution puis elle devint le temple de la Raison et de l'Etre Suprême. Elle fut également légèrement endommagée lors des bombardements des Alliés en 1944 pour réduire les dernières poches de résistance allemande dans la ville.