Exposée au sud, baignée par le Lot, abritée des vents froids de l'Aubrac, la commune de Castelnau de Mandailles a connu une occupation humaine précoce. C'est sur son territoire qu'a été découverte l'une des plus anciennes traces de l'occupation humaine en Rouergue. A un kilomètre en aval de Mandailles, Jean Maury a mis à jour quatre choppers (galets sommairement aménagés) en schiste local que l'on situe à l'acheuléen (paléolithique inférieur).
Un tumulus détruit, sur les pentes du Puech du Barry, témoigne aussi d'une occupation antérieure à l'époque antérieure à l'époque celtique. Comme dans tout le Rouergue, la civilisation gallo-romaine a laissé des traces sous forme de "tegulae" apparaissant lors de labours ou de travaux d'excavation, particulièrement à Artignac ; la toponymie gallo-romaine est aussi présente sur tout le territoire (Vinnac, Artignac). Cependant, et la toponymie le révèle, l'occupation véritable se met en place au moyen âge. Très tôt, le prieuré de Cambon devait fédérer l'ensemble des villages qui allaient devenir la commune de Castelnau de Mandailles. Peut-être existait-il aussi à l'origine une seconde église signalée le 20 fructidor an XII, et la trace en est aujourd'hui perdue (s'agirait-il des curieuses ruines situées près d'Artignac?).
Construits vers le XIè siècle, les châteaux de Mandailles et de Castelnau allaient rapidement grouper autour de leurs murailles une population qui allait faire de ces villages des concurrents de Cambon. Il semble qu'à l'origine, comme la plupart des châteaux, ceux-ci ne fussent que des forteresses secondaires tenues par des petits seigneurs, vassaux des barons de Calmont. La famille Sohenrel, de petite chevalerie, tenait de nombreux biens dans les deux châtellenies au XII et XIIIè siècle. Castelnau semble de par son nom, plus récent, mais rapidement, le site de ce nouveau château allait attirer une population plus importante. L'installation de ces deux châteaux, la formation de leurs mandements allait structurer la région sans égard pour l'antique paroisse de Cambon, située à leur limite.
En Rouergue, les communautés, ancêtres de nos communes, qui se mettent en place au môyen-âge, seront le reflet du découpage féodal. Castelnau et Mandailles, châtellenies dépendantes de la baronnie de Calmont d'Olt, possédaient dès le XVIè siècle des prud'hommes dont le premier rôle était la levée des impositions. les réunions étaient alors publiques et la communauté de Mandailles se réunissait sur la place du village.
Après l'achat le 30 Mai 1741 par Jean-Baptiste de Currières au marquis de Bourbon-Malauze, baron de Calmont d'Olt, de sa baronnie de Saint-Côme, la terre fut errigée en marquisat en septembre 1747. Les communautés de de la terre de Calmont étaient à cette époque réunies, formant un immense ensemble, impossible à gérér.
Cette union ne dura pas. Beaucoup trop vaste, "la communauté de Roquelaure" ou "terre de Castelnau" fut scindée par arrêt du conseil du roi le 29 Février 1752. Cependant Castelnau et Mandailles restaient accolées aux communautés de Saint-Côme, les Cuns et Flaujac. Il coûta 30.000 livres, somme absolument considérable pour ces pauvres communautés de paysan, et des années de discussions pour obtenir enfin, le 17 Mars 1782, la reconnaissance des deux communautés de Castelnau et de Mandailles.
Un dernier arrêt du roi, daté du 11 Septembre 1789, ordonnait "que la communauté de Saint-Côme" désunie de celle de Roquelaure et terres de Castelnau sera divisée pour former à l'avenir cinq communautés distinctes et séparées: 1e Saint-Côme; 2e Castelnau; 3e Mandailles; 4e Aunac; 5e Flaujac".
La loi du 14 Décembre 1789 substituait aux anciennes communautés, régies par des coutumes fort disparates héritées de l'époque médiévale, de nouvelles circonscriptions, les communes. En Rouergue, les communes succédèrent sans difficultés aux anciennes communautés. Castelnau et Mandailles furent comprises dans le ressort du canton de Saint-Côme.
En l'an II, de nombreuses communes de l'Aveyron furent réunies pour rationaliser leur administration et probablement avec des intentions politiques les petites communautés étant formées de municipalités contre-révolutionnaires. La municipalité de Mandailles étant particulièrement surveillée par les administrateurs du département pour sa complaisance envers "les brigands", déserteurs, royalistes de prêtres réfractaires.
Le 17 germinal an II, le conseil municipal de Mandailles s'inquiétait d'un projet de réunion avec Castelnau. Malgré les rapides et nombreuses protestations, l'union eût lieu. Mandailles perdait sa municipalité par arrêté de l'agent national du district, le 24 germinal. Cependant, après de nouvelles pétitions, les deux communes furent une fois encore désunies le 24 fructidor an II.
L'une des premières décisions de Sainthorent, 1er préfet de l'Aveyron fût, par son arrêté, une profonde réorganisation du découpage communal.. Castelnau et Mandailles furent encore une fois réunions sous le nom de Mairie de Castelnau. La vieille maison commune de Cambon continuait à être utilisée mais chaque commune conservait son propre lieu de réunion.
L'arrêté de Sainthorent n'ayant jamais été légalisé par le ministre de l'intérieur, ce n'est que par l'ordonnance royale du 18 Juin 1843 que la réunion des deux communes sous le nom de Commune de Castelnau, devenait officiel. Castelnau était érigée en chef lieu de commune.
Le 7 Septembre 1954, un décret donnait le nom de Castelnau de Mandailles à la commune, retrouvant par là ses racines historiques. Le 18 juin 1989, le conseil municipal décidait la suppression du sectionnement "pour faire disparaître les rivalités qui avaient pu se manifester autrefois et depuis 1843 entre les deux sections". C'était l'aboutissement de l'union d'une population rassemblée depuis un millénaire autour de l'église de Cambon.