Le castrum médiéval de Capdenac a succédé à un oppidum qui a connu une importante occupation protohistorique puis antique, qui s'est prolongée pendant le haut Moyen Age. Il apparaît dans la Vita de saint Géraud d'Aurillac (vers 855 - vers 918), à l'occasion d'une guérison miraculeuse. C'est en empruntant une voie romaine devenue un « cami romieu » que le char transportant une table d'autel en marbre de Narbonne à Limoges serait passé par Capdenac (L. d'Alauzier, 1966, p. 144).
En 1095, les seigneurs de Capdenac font partie des « avoués-défenseurs » de l'abbaye de Figeac qui sont excommuniés par le pape Urbain II. En 1180, pour s'opposer à l'avancée des troupes du roi d'Aragon, le comte de Toulouse campe devant le castrum de Capdenac : on compte parmi les nobles engagés à ses côtés un Adhémard de Capdenac et un Bertrand de Balaguier, qui appartiennent sans doute à des familles qui se partagent la seigneurie. De fait, les coseigneurs semblent relativement nombreux : lors de l'hommage à Simon de Montfort en 1214, ils sont mentionnés collectivement, et ce ne sont pas moins de quinze coseigneurs qui figurent sur la charte des coutumes octroyées en 1291, dont quatre Balaguier et cinq Capdenac. Le castrum reste partagé entre une multitude de coseigneurs jusqu'à la Révolution.
D'abord aux comtes de Toulouse, la suzeraineté passe aux rois de France qui confirment à plusieurs reprises les privilèges des habitants de Capdenac au cours du 14e siècle, mais la place forte est placée sous l'autorité des comtes d'Armagnac devenus comte de Rodez en 1302, qui la conservent jusqu'en 1518, où elle est vendue à Galiot de Genouillac, seigneur d'Assier. Devenue citadelle protestante, elle fait partie des places de sûreté accordées aux Réformés par l'Edit de Nantes.
Des consuls sont mentionnés dès 1243 (A. Teulet, 1866), et la charte de 1291 n'est peut-être qu'un renouvellement des coutumes ; ils ont une maison commune en 1303 (G. Picot, 1901). Un registre notarial des années 1270 (BNF, N.A.F. 10188) fait en outre apparaître un hôpital et une maladrerie. Comme c'est sans doute le cas pour bien des petites villes du Quercy, des marchands de Capdenac participent au grand commerce, aux côtés de ceux de Figeac, achetant des draps de Provins à la fin du 13e siècle, ou opérant à Castelnaudary, Montpellier et Chalon-sur-Saône vers 1320 (L. d'Alauzier, 1954) ; le port sur le Lot (mentionné en 1267 : A. Molinier, 1894) permet le transport des vins de la contrée jusqu'à Bordeaux, et de là jusqu'en Flandres (L. d'Alauzier, 1954). Des habitants de Figeac se réfugient à Capdenac dans les années 1360, pour échapper à la peste (G. Foucault, 1994).
Si la base d'une tour de l'enceinte et l'arcade, à gros quart de rond sur l'angle, d'une maison de la rue de la Commanderie (IA46101449) pourraient dater de la fin du 12e siècle, la majeure partie des constructions médiévales du castrum appartiennent au 13e siècle, ou au début du 14e siècle.
