Mentionnée seulement pour la première fois en 889 (alors que l'existence de l'évêché est attestée dés 356 par la tenue à Béziers d'uri ·concile), à l'occasion d'une donation "in opus Sancti Nazarii" la cathédrale s'élevait en dehors de l'enceinte de la ville antique.
On ne sait rien de la cathédrale antérieure à l'époque romane si ce n'est la mention de 889 et celle en 977, d'une autre donation effectuée par le vicomte de Béziers, Guillaume, pour la poursuite des travaux, et l'achèvement de l'église.
Dés le second tiers du XIIe siècle, les dons pour la construction d'une nouvelle église commencent à apparaître. La cathédrale romane, dont la chanson de la Croisade de Guillaume de Tudèle nous précise le nom du maître d'oeuvre, Gervais, possédait une nef unique de trois travées couverte d'une voûte en berceau sur doubleaux le choeur également voûté était terminé par un chevet plat. Elle était peut-être fortifiée. Le cloître, construit vers 1150, s'accolait au flanc sud de l'église. Cet ensemble faisait partie au XIIe siècle du quartier canonial qui regroupait aussi, sous la protection d'une enceinte, l'église Sainte-Marie du Siège (formant avec Saint-Nazaire une cathédrale double), le palais épiscopal, les maison du chapitre et un vaste cellier.
Réutilisant à l'Est la fortification du Bas-Empire, l'enceinte canoniale présentait au sud un mur garni de mâchicoulis sur contreforts et dont la partie orientale sera remaniée lors de la construction du second cloître.
La prise de Béziers en juillet 1209 par les croisés d'Innocent III lors de la lutte anti-hérétique entraîna la destruction, par incendie et l'effondrement des voûtes, de l'église de maître Gervais.
C'est en, 1215, sous l'épiscopat de Raymond Lenoir, qui versa annuellement 1000 sols melgorien pour la réfection de Saint-Nazaire, que débutèrent les travaux de reconstruction. On intègre alors dans la nouvelle en 1354 pendant la nuit de Noël, entrainera sa reconstruction au cours de la seconde moitié du siècle.
La fin du XIVe siècle verra l'achèvement d'une partie de la façade occidentale, avec les deux tours d'angle et le portail, la construction d'un nouveau cloître à l'emplacement du cloître roman et d'une première salle capitulaire, doublée au XVe siècle d'une seconde établie en étage par l'évêque Guillaume de Montjoie.
C'est à ce même prélat que l'on doit la construction, entre 1444 et 1451, de la chapelle des Douze-Apôtres, devenue sacristie en 1599.
Les guerres religieuses de XVIe siècle, se solderont par le pillage de l'église, en 1562, par les troupes protestantes et la destruction de l'orgue mis en place au cours de la première moitié du siècle.
Enfin, au XVIIIe siècle, le choeur sera transformé. L'installation en 1758-1759 d'une colonnade de marbre et d'une gloire va entralner la modification des fenêtres gothiques et le bouleversement des vitraux médiévaux.
