Ce serait au début du XI ème siècle qu’aurait été construite une partie de l’église actuelle, sur l’emplacement de l’ancienne chapelle Sainte-AGATHE. Elle n’avait qu’une seule nef dessinée par de basses arcades à plein cintre et son chœur était tourné vers le Levant selon l’usage liturgique. Faiblement éclairé, l’édifice portait à la méditation et pour y accéder, il fallait traverser le cimetière qui s’étendait tout autour du sanctuaire.
La nécropole était entourée d’un épais mur percé de meurtrières horizontales et les habitants devaient sans doute s’y réfugier pour résister à toute attaque de brigands ou d’ennemis. C ’est toujours vers cette époque que les paroissiens firent construire le lourd beffroi carré que nous connaissons encore aujourd’hui, et du haut duquel ils pouvait surveiller la forêt environnante où s’élève de Longuyon moderne, et sonner le tocsin en cas de danger.
Au début du XIIème siècle, une charte de REPON, autre archevêque de Trèves, confirme que la paroisse de Longione, après avoir longtemps dépendu de l’église Saint-PIERRE de Trèves, passe sous la tutelle des bénédictins de Sainte-MARIE aux martyrs (de Trèves) pour deux tiers et l’autre tiers, de l’abbaye d’Orval qui donne tout pouvoir d’administration aux moines de la Grange de Villancy.
En 1270, les chanoines envisagent d’agrandir le sanctuaire, mais les travaux ne débutent qu’en 1275 car l’argent manque, bien que le comte THIEBAULT de Bar ait autorisé les ecclésiastiques à percevoir de fortes dîmes pour réaliser ce projet .Toutefois, il fallut réduire les exigences fiscales car les bourgeois de Longione refusaient de payer.
Entre 1275 et 1287, le sanctuaire vit sa nef doubler de longueur, et il lui fut adjoint deux nefs collatérales éclairées par de longues fenêtres à lancettes. Le chœur forma une abside polygonale et sur le côté sud, on éleva une tourelle en pierres de taille afin d’y loger un escalier qui conduit au-dessus des voûtes ogivales.
C’est en 1287, le 20 avril probablement, que la collégiale fut consacrée à Sainte-AGATHE.
Il existe une statue de pierre sculptée de la Martyre de Catane ; elle date de cette époque, elle est de très bon style et de bonne facture.
En 1270, le comte THIEBAULT avait affranchi la cité qui s’administra selon la loi de BEAUMONT datant de 1182.La justice était rendue par deux hommes élus, l’un par 40 Bourgeois et l’autre par toute la communauté. A ces deux élus s’ajoutaient trois Bourgeois de la Ville et un de Noërs, de sorte qu’avec le Maïeur et le Lieutenant, c’étaient 8 personnalités qui prêtaient serment devant le Prévot.
Le Maïeur réglait l’usage du moulin banal, fixait le prix de vente des denrées, avait autorité en matière de police sanitaire et frappait d’amende tout contrevenant. Il était aidé dans sa tâche par deux gardes forestiers. Lorsque le Prince se déplaçait, le Maïeur et les Echevins (adjoints), au nom de la ville, étaient tenus d’entretenir son escorte et seuls, les Drapiers échappaient au paiement des 12 deniers forts réclamés à chaque Bourgeois, lors de sa visite.