Noyon est à l'origine une ville romaine de garnison, dont le castrum a été fortifié vers la fin du 3e siècle. Les premiers évêques s'y sont établis, avec la cathédrale, lorsque le siège du diocèse a été transféré de Saint-Quentin à Noyon au 6e siècle, vraisemblablement à l'initiative de saint Médard. L'évêché de Tournai a alors été rattaché à celui de Noyon jusqu´en 1146.

La ville et son évêque étaient très liés à la royauté franque, dès le règne de Dagobert, sous l'-´épiscopat de saint Eloi (641-660). Charlemagne y fut couronné roi de Neustrie, en 768, et Hugues Capet y fut sacré roi le 3 juillet 987.

Plusieurs cathédrales se sont sans doute succédé au cours du Haut Moven Age. La cathédrale romane a été ravagée dans l'incendie de la ville, en 1131. L'évêque, qui était le seigneur de la ville, donna l'autorisation d'étendre la construction à l'extérieur de l'enceinte antique pour l'agrandir. Noyon s'était déjà beaucoup étendu au-delà des murs, qui semblent avoir perdu leur caractère défensif au 12e siècle. Jusqu'à la fin du 19e siècle, l'enceinte venait buter sur le bras du transept, près de sa porte orientale, et on sait qu'elle s'incurvait ensuite plus à l'ouest. Le bras nord du transept et le sanctuaire actuel ont ainsi pu être élevés extra-muros sur un terrain dégagé.

On ignore quand a débuté la reconstruction de la cathédrale. L'évêque, Simon Ier, frère du compte Raoul de Vermandois et cousin du roi, fonde l'abbaye cistercienne d´Ourscamp (1132-1133) mais il est suspendu en 1142, quatre ans avant le détachement de l'évêché de Tournai. Les chanoines du chapitre cathédral auraient pu gérer et financer la plus grande part du chantier, mais l'analyse du style du chevet de la cathédrale, qui en constitue la partie la plus ancienne, paraît être postérieur à celui de Saint-Denis, élevé de 1140 à 1144. On peut donc supposer que, dans un premier temps, l'ancienne cathédrale, située approximativement sous la nef actuelle, est réparée pour ne pas interrompre la célébration du culte, tandis qu'on fait des projets et qu'on réunit les ressources financières. Les fondations en grès du sanctuaire forment un énorme socle de 5 m de profondeur, destiné à un édifice très lourd, et les chapelles du pourtour du sanctuaire, élevées en premier, ont une structure beaucoup plus épaisse et un décor différent du reste du chevet ; aussi pense-t-on qu'il faut distinguer un changement de parti en cours de travaux.

Mais cela ne permet guère de préciser la date du début du chantier avant ou après 1148.

Les travaux avancent certainement plus vite sous l'épiscopat de Baudoin II (1148-1167). C'est un ami de Suger, abbé de Saint-Denis. En 1157, il fait transférer les reliques de saint Eloi dans une nouvelle châsse mais rien n'indique cependant que cette translation corresponde à l'achèvement du sanctuaire. Il faut s'en remettre à l'analyse architecturale et à des comparaisons avec d'autres monuments pour établir une chronologie relative.

Le chevet est certainement terminé sous Baudoin II et le transept commencé et achevé sous Baudoin III (1167-1174). La dernière travée de la nef est constituée, d'est en ouest, sous l'épiscopat de Renaud (1174-1188) et complétée sous celui d'Etienne Ier (1188-1221), fils et frère de chambellans du roi. En 1204, quatre nouveaux marguilliers sont nommés pour le service de la cathédrale, certainement très avancée. Le massif occidental de la façade doit dater du premier tiers du 13e siècle. La sonnerie des grandes cloches est réglementée en 1231, ce qui confirme l'achèvement du beffroi dans l´une des tours occidentales.

Un incendie dévaste une partie de la ville en juillet 1293 et affecte la cathédrale, au moins sa façade et le côté nord de la nef, car les deux piliers détachés devant le porche occidental sont ajoutés en renfort et les parties hautes de la tour nord-ouest sont reconstruites. En 1299, des chapelles latérales sont aménagées entre les contreforts du côté nord de la nef. Des travaux d'embellissement sont effectués vers la fin du 13e ou au début du 14e siècle. Les portails latéraux de la façade ouest sont remaniés, un jubé est élevé, au 14e siècle, à l´entrée de la croisée, et une chapelle est fondée en 1297, au sud de la nef.

La cathédrale n'eut pas à subir d´attaques directes durant la guerre de Cent Ans, mais souffrit certainement d'un manque d'entretien, car des comptes et des documents d'archives indiquent que d'importantes réparations sont entreprises à l'issue de la guerre, vers 1460-1476. Le chapitre fait venir des experts, Jean Turpin, maître maçon à Péronne, le maître charpentier Thomas Noiron, puis les maîtres maçons Florent Bleuet de Reims et Jean Massé de Compiègne. En 1476, Pierre Tarissel, maître des œuvres de la ville d'Amiens est consulté à son tour. Plusieurs voûtes dans la nef et dans le bras sud du transept sont alors reconstruites, les contreforts et les arcs-boutants de la nef ainsi que la tour nord de la façade ouest sont repris. Dans le sanctuaire, il faut réparer la tour nord qui jouxte le transept, refaire une voûte voisine au niveau des tribunes, reprendre en sous-œuvre les piliers des travées droites du chœur et reconstruire les arcs-boutants qui étayent les tribunes.

Aux 16e et 17e siècles, on se contente d'ajouter deux nouvelles chapelles au sud de la nef, en revanche, au 18e, ont lieu des modifications plus profondes. Les deux tours situées à l'entrée du chœur sont arasées au niveau des toitures, en 1723 et entre 1747 et 1753, les fenêtres hautes sont refaites, les arcs-boutants supérieurs sont démolis et remplacés par des contreforts incurvés et ornés de pots à feu. De plus, un épais badigeon blanc grisâtre est étendu à l'intérieur, aussi bien sur les chapiteaux sculptés que sur les murs, et recouvre les restes de la polychromie médiévale. Des niches ornées de statues sont aménagées au niveau inférieur des bras du transept.

En 1790, l'évêché est supprimé et n'est pas rétabli quand la cathédrale est rendue au culte en 1795. Entre-temps, la plupart des vitraux sont détruits et la sculpture des portails est martelée ou abattue.

Classée Monument Historique dès 1840, Notre-Dame de Noyon fait l'objet de plusieurs campagnes de restauration au 19e siècle.

L'extérieur du chevet est de nouveau repris, ses fenêtres hautes sont modifiées, au moins du côté sud. Le bras sud, restauré en 1843, est transformé en 1899 par son dégagement. Le mur d'enceinte qui le touchait et l'escalier, qui le reliait à la chapelle épiscopale, sont démolis et le niveau inférieur de l'hémicycle, qui comportait des niches et des portes, est remodelé pour faire place à un rang de fenêtres. Le portail oriental est retouché. La tour sud, contre le chœur, est aussi intégralement reconstruite.

En 1918, la cathédrale est bombardée d'obus qui percent des voûtes, sectionnent des piliers et finissent par embraser les toitures, entraînant l'écroulement de la plupart des voûtes hautes. La remise en état, très scrupuleuse, sous la direction de l'architecte André Collin, est achevée avant la Seconde Guerre mondiale qui, heureusement, épargne le monument. En dépit des dommages subis, des remaniements et des réfections, la cathédrale préserve l'essentiel de son architecture des 12e et 13e siècles, ainsi qu'un remarquable mobilier.