Najstarší písomný doklad o Castelsarrasin, ako Castel Sarracenum, pochádza z roku 961. Je zapísaný v závete Raymonda II. z Rouergue, v ktorom daroval kostol Saint-Sauveur kláštoru Moissac.
Castel Sarracenum ("Saracénsky hrad") dostal toto meno preto, lebo hrad bol postavený v saracénskej ére.
V ranej histórii mesta sa viedlo mnoho vojen:
- proti Angličanom až do konca 12. storočia;
- albigénska krížová výprava v prvej polovici 13. storočia a
- pastierskej výpravy v roku 1320, keď bolo zabitých mnoho Židov žijúcich v meste.
Neskôr región zasiahla storočná vojna. Väčšina obyvateľov mesta boli katolíci, ale v jeho okolí žilo aj mnoho protestantov. Počas francúzskych náboženských vojen v 16. storočí tu boli časté boje medzi týmito dvoma skupinami.
V nasledujúcich storočiach, až do Francúzskej revolúcie, bol v regióne väčší pokoj.
V rokoch 1790 až 1795 bol Castelsarrasin hlavným mestom okresu Castelsarrasin v departemente Haute-Garonne. V roku 1808, keď bol vytvorený departement Tarn-et-Garonne, sa okres Castelsarrasin stal súčasťou nového departementu.