the area became part of the Roman Empire and a Roman vicus came into being here, named, according to legend, after a Celt called Cruciniac, who transferred a part of his land to the Romans for them to build a supply station between Mainz (Mogontiacum) and Trier (Augusta Treverorum). Kreuznach lay on the Roman road that led from Metz (Divodurum), by way of the Saar crossing near Dillingen-Pachten (Contiomagus) and the Vicus Wareswald, near Tholey to Bingen am Rhein (Bingium). About AD 250, an enormous (measuring 81 × 71 m), luxurious palace, unique to the lands north of the Alps, was built, in the style of a peristyle villa. It contained 50 rooms on the ground floor alone. Spolia found near the Heidenmauer ("Heathen Wall") have led to the conclusion that there were a temple to either Mercury or both Mercury and Maia and a Gallo-Roman provincial theatre. According to an inscription and tile plates that were found in Bad Kreuznach, a vexillatio of the Legio XXII Primigenia was stationed there. In the course of measures to shore up the Imperial border against the Germanic Alemannic tribes who kept making incursions across the limes into the Empire, an auxiliary castrum was built in 370 under Emperor Valentinian I. Middle Ages After Rome's downfall, Kreuznach became in the year 500 a royal estate and an imperial village in the newly growing Frankish Empire. Then, the town's first church was built within the old castrum's walls, which was at first consecrated to Saint Martin, but later to Saint Kilian, and in 1590, it was torn down. According to an 822 document from Louis the Pious, who was invoking an earlier document from Charlemagne, about 741, Saint Martin's Church in Kreuznach was supposedly donated to the Bishopric of Würzburg by his forebear Carloman. According to this indirect note, Kreuznach once again had a documentary mention in the Annales regni Francorum as Royal Pfalz (an imperial palace), where Louis the Pious stayed in 819 and 839. Kreuznach was mentioned in documents by Louis the Pious (in 823 as villa Cruciniacus and in 825 and 839, as Cruciniacum castrum or Cruciniacum palatium regium), Louis the German (in 845 as villa Cruzinacha and in 868 as villa Cruciniacum), Charles III, "the Fat" (in 882 as C[h]rucinachum, Crutcinacha, Crucenachum), Arnulf of Carinthia (in 889), Henry the Fowler (in 923), Otto I, Holy Roman Emperor (in 962 as