Bourg médiéval, "Un des plus beaux villages de France", il a conservé de beaux témoignages de son passé de bastide comtale puis royale. Première bastide du Rouergue, construite à l'initiative du comte de Toulouse, elle est venue se greffer en 1231, autour du monastère du XIème siècle fondé par Ozile II de Morlhon. Une des cinq bastides ("villes neuves" médiévales au plan d’urbanisme novateur) du département. Ces bastides furent construites aux XIIIème et XIVème siècles pour faire face à la forte croissance démographique dans la région (315 ont été construite entre 1229 et 1373). La ville, fortifiée au XIVème siècle a gardé deux vestiges importants, la tour-porte Cardalhac et la porte Haute. La place centrale, des Conques, montre encore ses arcades et de belles maisons, témoins de l’architecture du XIVème siècle. Le principal monument demeure l’église du Saint-Sépulcre, construite dès la fin du XIème, au XIVème siècle, l’abside a été détruite et remplacée par une nef gothique beaucoup plus lumineuse, car il ne reste presque plus rien de l’ancien monastère. Villeneuve doit sa naissance au pèlerinage sur les Lieux Saints, à Jérusalem, que fit le seigneur du lieu, Ozile de Morlhon, soucieux du salut de son âme et de celle de ses ancêtres, il offrit au patriarche Sophronius de construire, sur ses terres de l'Aveyron, un monastère fonctionnant sous la règle du Saint Sépulcre.
