Située vis-à-vis du Palais royal, l’église Saint-Barthélemy fut de tout temps considérée comme l’une des plus anciennes de Paris. Bien que souvent nommée comme vraisemblablement construite vers 890 par le comte de Paris, Eudes, son origine est peut-être plus ancienne. Quelle que soit son histoire antérieure au comte Eudes, celui-ci en fit une collégiale de chanoines.
Vers 956/966, Hugues Capet, comte de Paris, duc de France et bientôt roi, la choisit pour y déposer plusieurs reliques de saints venues de Bretagne afin de les mettre à l’abri des incursions normandes. Parmi ces reliques, on comptait celles de saint Magloire, évêque de Dol. Le vocable de Saint-Magloire vint donc se rajouter à celui de Barthélemy porté jusque là par l’église.
En 1138, la dépouille de l’évêque et les diverses reliques furent transportées dans une autre chapelle que les chanoines possédaient sur la route de Saint-Denis (n° 82, de l’actuelle rue St-Denis). Les moines de St-Barthélemy-St-Magloire y déménagèrent aussi (► abbaye Saint-Magloire).
L’église reprit alors son ancien nom, fut érigée en paroisse et devint l’église paroissiale de tout l’enclos du Palais, sauf de la partie ressortissant à la paroisse spéciale de la Sainte-Chapelle. Construite avant la Sainte-Chapelle, le roi de France en fut son premier paroissien et, en 1787, on voyait l’écu fleurdelisé sur le fronton de la nouvelle façade.
Elle avait son entrée juste en face de la grande salle du Palais dont elle était séparée par la rue Saint-Barthélemy.
Au début du 14ème siècle, tombant en ruines, elle fut reconstruite et notablement agrandie par l’adjonction de la chapelle Notre-Dame-des-Voutes qui devint le chevet de l’édifice.
Bien que réparée à plusieurs reprises (1550, 1730, 1740, 1772), son état de vétusté était tel qu’une restauration plus conséquente fut commencée en 1787. La façade était terminée quand la Révolution vint interrompre les travaux. Les bâtiments inachevés furent vendus comme bien national le 12 novembre 1791 et démolis en partie l’année suivante.