Le premier château du Cateau-Cambrésis fut construit au 11ème siècle. Il est sans cesse détruit et reconstruit, au gré des conflits subis. Le Palais Fénelon actuel date de la fin du 18ème siècle, édifié par l’architecte Alexandre-Théodore Brongniart qui transforme la résidence des archevêques de Cambrai à partir de 1777.

La façade du palais est animée par des jeux de couleurs : l’appareillage en "rouges barres"(alternance de 4 rangs de briques rouges et de pierre blanche calcaire) est typique de l’architecture du Nord de la France au 18ème siècle. Les fenêtres sont strictement alignées, la surcharge décorative a disparu et les fenêtres médiévales à meneaux sont remplacées par des menuiseries en bois.

L’entrée est marquée par un fronton triangulaire côté cour intérieure et un fronton semi-circulaire côté jardin, symboles de la noblesse du bâtiment et du statut élevé de ses occupants. Les toitures d’ardoises, les grandes cheminées et le soubassement en grès accentuent la polychromie du bâtiment.

Côté jardin, l’aile de retour droite du château donne aujourd’hui accès à l’arrière de l’ancien marché couvert acheté par le Département en 2012. Côté cour, un portail monumental jouxte sur la gauche l’ancienne conciergerie, elle-même adossée au marché couvert.

Transformé en caserne pour l’armée autrichienne pendant la Révolution française, une filature de coton s’installe au château en 1806, avant de devenir une école à la fin du 19ème siècle et un musée en 1982, le musée Matisse actuel.