La présence d’une muraille à Cambrai est abordée dans les gestes des évêques de Cambrai (Gesta pontificum (sive episcoporum) Cameracensium) commandés par l’évêque de Cambrai, Gérard Ier en 1024. Dans ce texte y est faite la mention de l’évêque de Cambrai Dodilon (888-902) qui fait agrandir l’enceinte de la ville pour pouvoir englober l’abbaye de Saint-Aubert alors extra-muros et ainsi protéger la cité et éviter de nouveaux raids dévastateurs. L’emplacement de cette abbaye (aujourd’hui place du Neuf-Octobre) se situe à l’Est du noyau ancien. L’extension de l’enceinte passe par La Grande Rue Vanderburch, par la Place du Neuf Octobre ainsi que par la rue des Clefs, ce qui complète le tracé de l’enceinte gallo-romaine. 

Cet agrandissement correspond donc à la toute première évolution du tracé originel de l’enceinte de Cambrai. Sous Dodilon, il n’y a que cet agrandissement vers l’Est, les autres parties de l’enceinte fortifiées, front Sud, Nord et Ouest, sont donc vraisemblablement uniquement entretenues. Cette extension a certainement dû se faire à partir de terre, de bois ou de pierre.

Au milieu du XI^e siècle, l’enceinte connaît un agrandissement assez conséquent. La création et le développement de l’abbaye du Saint-Sépulcre, ainsi que des églises Saint-Georges, Saint-Marie-Madeleine et Saint-Nicolas entre le castrum et l’abbaye Saint-Géry située à environ un kilomètre au Sud témoigne d’un essor urbain hors de l’enceinte de Cambrai. Entre 1052 et 1076, l’évêque Liebert (1051-1076) élargit l’enceinte de la ville dans le but d’englober ces nouvelles créations.

Durant les siècles qui suivent, l’intérêt pour ces défenses diminue. C’est avec le déclenchement de la guerre de Cent Ans que l’intérêt pour les fortifications des villes renaît. Ce contexte assez hasardeux et violent explique l’investissement défensif que les villes concernées par la guerre réalisent.

Les villes élargissent les fossés et les remparts avec de la terre et transforment le plan des tours qui passent d’un plan quadrangulaire à semi-circulaire.

C’est avec les travaux de la porte du Saint-Sépulcre à partir de 1391 que débute une campagne de modernisation de l’ensemble fortifié. La porte, trop désuète, va être entièrement rebâtie selon les normes architecturales défensives de l’époque. Vont venir s’y greffer un pont-levis, des herses, des vantaux ou des assommoirs. Par la suite, c'est la porte d’eau des Arquets qui fut reconstruite. Entre 1401 et 1403, c’est la porte Saint-Ladre qui se voit moderniser.

La plupart des tours et portes ne possèdent que deux étages. Leur hauteur ne dépasse pas les 15 mètres maximum à partir du fond des fossés. Enfin, ces tours et portes sont percées de nombreuses archères à bêches et de fenêtres.

En ce qui concerne les courtines, pour la plupart elles ont été reconstruites dans les années 1400. Encore une fois dans l’optique des évolutions techniques de l’époque, ces courtines mesurent environ huit mètres et sont renforcées par de nombreuses tours qui dépassent de trois à quatre mètres le parapet. Le front Est de ces courtines est, contrairement au reste du tracé de l’enceinte, d’un aspect brisé.

Sur ces courtines, en plus de tours, se trouvent des échauguettes, notamment sur le front sud de l’enceinte, en face de la zone marécageuse.

Sur la pointe nord de la ville, et extérieur à l’enceinte se trouve un système de défense incontournable pour l’époque, un château fort. C’est au XII^e siècle, sans doute vers 1220-1230 que le château de Selle est bâti à la suite d’une révolte bourgeoise. Cette construction est assez atypique pour l’époque. Elle est bâtie selon un plan pentagonal irrégulier. 

Il est entouré d’un fossé inondable par les eaux de l’Escaut tout proche. Sa muraille défensive s’élève à environ 15 mètres de hauteur, la norme à une époque où plus les défenses sont hautes, plus la défense est assurée. Cette muraille se voit renforcée par six tours positionnées aux angles. Sa muraille et ses tours sont assez novatrices sur certains points. Ses courtines embarquent en leur sein deux niveaux de passages distincts. En ce qui concerne les tours, à la différence des tours construites entre 1390 et 1420, elles se divisent en trois niveaux, toutes percées d’embrasures de tirs pour armes mécaniques. Bien qu’extérieur à l’enceinte, le château de Selle garde une place importante dans le système défensif de la ville.

La pierre de grès a été systématiquement utilisée, car plus résistante à la sape et aux aléas climatiques, d’autant plus que les sols de Cambrai regorge de ce matériau. Après la fin des travaux de modernisation des fortifications, l’ensemble de l’enceinte à la fin du XV^e siècle s’étend sur une surface d’environ 4 000 mètres carrés, réunissant sept portes et environ 50 tours.

Comme la plupart des villes fortifiées de l’époque, Cambrai se retranche désormais derrière une épaisse et haute ceinture fortifiée.