Une première église accueillit à Vieux au milieu ou au début du 3e quart du 9e siècle les reliques de saint Eugène, saint Amarand et sainte Carissime. La date du transfert des reliques depuis l'environnement immédiat d'Albi n'est pas connue mais l'église est mentionnée en 861, ainsi que les reliques, dans un legs de la comtesse de Rouergue, Sénégonde (Biget, 1990, p. 20). L'église est alors sous le vocable Saint-Aubin. Aux 9e et 10e siècles, un abbé était à la tête d'un chapitre de quatre chanoines. En 931, il est mention de reliques de deux autres saints, saint Longin et saint Vindémial (de Lacger, 1922, p. 222). L'église acquiert un rayonnement certain au 10e siècle, elle bénéficie des libéralités testamentaires des comtes de Toulouse-Rouergue. A la fin du 10e siècle, un prévôt remplace l'abbé (de Lacger, 1922, p. 228). La sauveté de Vieux est créée entre 1037 et 1041 (Biget, 1990, p. 27) et en 1078, le prieuré est uni à l'abbaye d'Aurillac par l'évêque Frotard. Ce n'est qu'en 1204 que l'évêque d'Albi put conclure un accord avec l'abbaye d'Aurillac pour retrouver l'église Saint-Eugène. L'église fut reconstruite selon toute vraisemblance dans le 1er quart du 14e siècle, sur le plan d'une vaste église à vaisseau unique de cinq travées couvert d'une charpente, clôturé par un choeur voûté d'ogives à une travée droite, bordée au sud et au nord d'une chapelle latérale voûtée d'ogives, et une abside polygonale. En 1340, la dignité de prévôt est supprimée et le chapitre cathédral institue en cette église un vicaire perpétuel et quatre donats (Rossignol, 1865, p. 323). En 1494, l'évêque Louis d'Amboise fit transférer les reliques de Vieux à la cathédrale d'Albi mais une partie des reliques furent laissées à Vieux ( Rossignol, 1865, p. 332). La limite du 15e et du 16e siècle correspond aussi à une intervention importante dans l'église Saint-Eugène. Les élévations de la première travée de la nef sont reprises lors de la construction d'un clocher-tour occidental, desservi par une tourelle d'escalier en vis pour les parties hautes, et un escalier intérieur donnant à la première salle, situé contre le revers de l'élévation occidentale. A sa base est élevée une chapelle latérale voûtée d'ogives bénéficiant d'un décor peint sur les murs sud, ouest et nord ainsi que sur la voûte. Un portail et une rose sont percés dans l'élévation sud de la deuxième travée. Deux chapelles latérales sont élevées au nord des deux dernières travées de la nef et trois chapelles, au sud des trois dernières travées de la nef. L'arcade de la chapelle nord du chour est alors fermée pour partie sur le chour, ménageant une petite porte en arc brisé et une salle voûtée en berceau est élevée à l'est. Une porte en arc segmentaire chanfreiné relie les deux parties. La chapelle sud est également fermée et abrite depuis la sacristie. En 1706, des aménagements sont entrepris dans la salle orientale de la chapelle nord du chour pour accueillir un retable et les reliques des saints (Rossignol, 1865, p. 332). Elle est dénommée alors "tombeau des saints". En 1810, des réfections sont apportées au plafond et à la toiture de l'église. En 1862, la cloche de l'église est refondue par Hypolite Boutet, fondeur à Albi (AD Tarn, 2 O 316/1). Entre 1867 et 1872, date de réception définitive des travaux réalisés sous la direction de l'architecte Rivet, une voûte en brique creuse est installée sur la nef et le chour (AD Tarn, 2 O 316/1). L'intérieur de l'église est plâtré en 1872 (AD Tarn, 2 O 316/1). Une partie de la charpente est refaite en 1894 (AD Tarn, 2 O 316/1). Entre 1880 et 1894, de nouveaux vitraux du maître verrier H. Fauré sont placés dans les baies du chour et des chapelles latérales de la nef. Probablement au début du 20e siècle, à la suite de la démolition de l'escalier intérieur, un nouvel escalier est installé dans une construction attenante au nord et relié à l'escalier en vis. L'église est classée Monument historique le 24 février 1906. La charpente est refaite en 1908 ainsi que les voûtes de brique et un fossé est creusé sur le pourtour de l'église pour la protéger de l'humidité. Le niveau du sol intérieur est exhaussé (CRMH, dossier). En 1941, le pourtour de l'église est assaini à nouveau (CRMH, dossier). En 1955, les trois premiers arcs diaphragmes de la nef sont consolidés par adjonction de béton et les voûtes en brique des premières travées de la nef sont démolies (CRMH, dossier). Les voûtes en brique des autres travées de la nef et du chour ont été démolies les années suivantes.