Le premier document connu retraçant l'histoire de Puycelsi  est, en 1180, l'acte de vente par lequel l'Abbé Pierre d'Aurillac, vendit cette seigneurie au Comte de Toulouse, Raymond V, à qui l'importance stratégique du site n'avait pas échappé : aux confins du Languedoc et de la Guyenne, tout proche des plateaux Cadurciens (Cahors). Les Comtes de Toulouse  fortifièrent la place et édifièrent un château, disparu depuis, et dont tout laisse penser qu'il fut leur préféré. Fidèle au Comte de Toulouse, Puycelsi résista par deux fois aux Montfort lors de la Croisade des Albigeois : à Simon de Monfort en 1211, puis à son frère Guy en 1213, qui ne purent s'emparer de la citadelle. Le traité de Meaux en 1229, qui marqua avec la fin de la Croisade des Albigeois la réconciliation de Raymond VII avec le jeune Roi de France Louis IX, stipulait que vingt-cinq villes ayant résisté aux vainqueurs devaient être détruites ; bien sûr, Puycelsi était du nombre. Commença alors un long démantèlement du village et de ses fortifications.