En 1591, Henri IV permet à Henri de La Tour d'Auvergne d'épouser Charlotte de La Marck, héritière du duché de Bouillon et de la principauté de Sedan. Tous les deux sont protestants.
Le prince de Sedan et duc de Bouillon, et son épouse Charlotte de La Marck, décident, en 1593, de fonder le Grand Temple neuf à Sedan. Bien qu'on ne connaisse pas le nom de l'architecte, on pense qu'ils ont demandé les plans du temple à Salomon de Brosse. Cette hypothèse a été faite parce qu'il a été l'architecte sur plusieurs bâtiments réalisés par le prince à Sedan.
La construction du temple est achevée en 1601. Il est alors ouvert au culte calviniste. Le vaisseau central est couvert d'un lambris en berceau et une tribune est construite sur la longueur du bas-côté droit. Elle servait à recevoir la famille du prince.
Le temple est agrandi en 1608 en lui ajoutant une tribune sur la longueur du bas-côté gauche. Elle était réservée à la noblesse, à la haute bourgeoisie et aux officiers.
À la suite de la participation au complot de Cinq-Mars contre Richelieu, le prince de Sedan, Frédéric Maurice de La Tour d'Auvergne-Bouillon, arrêté obtient son pardon en abandonnant la principauté au roi en 1642.
En 1685, l'édit de Fontainebleau abolit l'édit de Nantes. La religion réformée est interdite dans le royaume de France.
En 1688, l'archevêque de Reims, Charles-Maurice Le Tellier, demande à Robert de Cotte qui est de passage à Sedan de transformer le temple en église. Robert de Cotte dresse un plan d'église en croix latine. Il fait détruire les absides et transforme ce qui reste du temple en nef de la nouvelle église. Il fait ajouter un massif-antérieur comportant deux tours, un transept et un chœur. Le maître-autel est réalisé par les sculpteurs du roi, Bourlier, Dufour, Ergé.
Les tribunes sont supprimées en 1690, puis, a lieu en 1692 la bénédiction solennelle de la nouvelle église paroissiale, dédiée à saint Charles Borromée.
La tour gauche (Sud) de la façade est ajoutée en 1726. L'orgue est installée en 1768.
L'église devient la cathédrale d'un éphémère évêché constitutionnel des Ardennes en 1791. Le premier évêque de cediocèse de Sedan est Nicolas Philbert qui était le curé de la paroisse.
Pendant la Terreur, le culte est interdit en 1793. L'église après avoir été pillée devient le Temple de la Raison et le Temple de l'Être Suprême. En 1795 l'église est rendue au culte.
Le Concordat et ses articles organiques de 1802 supprime l'évêché des Ardennes.
La tour droite (Nord) de la façade est édifiée en 1822-1823, puis, finalement, en 1837, est ajoutée la tourelle de l'horloge entre les deux tours de la façade.