Dès le Moyen Age, le Cateau est à la fois refuge et résidence de campagne des évêques de Cambrai (Cambrai est érigé en archevêché en 1559). Le bâtiment actuellement connu sous l’appellation de palais Fénelon est à l’origine un château – Castellum Sanctae Mariae – élevé au début des années 1000, reconstruit dans les premières années du XVIe siècle. On lui donne alors le nom de château de Montplaisir – tout un programme -, flanqué de quatre pavillons résidentiels nommés Beauregard, Monsoulas, Monsecours et Belle Image. Ravagé par un incendie en 1563, le château est remplacé par un nouvel édifice appelé Cour l’Evêque.

En 1766, la paix revenue dans ce territoire passé depuis Louis XIV au royaume de France, l’archevêque de Cambrai, Léopold Charles de Choiseul, décide de se faire bâtir un nouveau palais finalement achevé quelques années plus tard par l’architecte Alexandre-Théodore Brongniart (1739-1813) – qui signe quelques années plus tard, en 1807, le palais de la Bourse à Paris. C’est lui qui fait élever la porte monumentale toujours visible aujourd’hui. 

Manière de souligner que l’archevêque de Cambrai Fénelon, s’il est régulièrement venu au Cateau comme ses prédécesseurs et successeurs, n’a donc pas connu le palais qui porte aujourd’hui son nom puisqu’il est mort en 1715.