Het is niet helemaal duidelijk waarom Karel de Grote uitgerekend deze locatie uitkoos om een van zijn paltsen te bouwen.

De gunstige geografische ligging aan een van de buitengrenzen van zijn rijk, op een heuvel en tegelijkertijd in een rivierbocht, speelde vermoedelijk mee; dit maakte de plek namelijk strategisch handig om de controle te houden over de nabijgelegen vijandelijke territoria, waar met name de Friezen en Saksen leefden. Enkele jaren daarvoor was Karel de Grote de Saksenoorlogen begonnen, waarbij onder meer het heiligdom Irminsul was vernietigd (volgens een passage uit de Annales Regni Francorum). Nu vielen er van Saksische zijde vermoedelijk wraakacties te verwachten.^[8]:9-10 Er was vanaf de Valkhofheuvel goed uitzicht over de Betuwe tot aan de zuidrand van de Veluwe.

Nog een andere factor van belang was mogelijk de waardigheid en allure die de plek in zekere mate moet hebben uitgestraald, ook dankzij de toen nog duidelijk aanwezige restanten van het castellum. Ten slotte kunnen er economische belangen hebben meegespeeld.^[4]:21/32

In dezelfde tijd, of één à twee eeuwen later, moeten er in deze omgeving meer burchten zijn gebouwd: Mergelp op de Duivelsberg, de burcht in Elten, de burcht in Kleef en de Monterberg bij Kalkar.^[7]:79

Het oudste bekende document waaruit men het bestaan van de Valkhofpalts afleidt is een oorkonde in de vorm van een giftbrief. Deze oorkonde is gedateerd op 7 of 8 juni 777 en werd opgesteld door Karel de Grote zelf in een "villa te N[i]umaga", uitgelegd als Nijmegen.^[9] Hierin schenkt hij onder meer enkele landgoederen aan de kerk van Utrecht (Traiectum). Inhoudelijk gaat de oorkonde over de gouw Flethite met daarin Villa Lisiduna (kennelijk Leusden, of het landgoed daarvan), en vier "foreesten", ofwel bossen waar het jachtrecht gold. Ook wordt er een rivier Hemus genoemd, die doorgaans wordt gelijkgesteld aan de Eem.^[10][11]

In de oorkonde staat voorts dat deze is opgemaakt in Niumago palacio publico. Over de precieze betekenis van publico in deze specifieke context is niet iedereen het eens; volgens de Duitse historicus Walter Schlesinger moet dit hier eerder worden vertaald als "koninklijk" dan als "openbaar" (in de zin van "van de overheid"). Het koningsambt zou zelf niet openbaar van karakter zijn geweest, en zich daarin onderscheiden van de "echte" overheid uit de Karolingische tijd.^[7]:83-84

In latere schriftelijke bronnen wordt afwisselend een palacium of villa vermeld, waarmee hetzelfde bouwwerk moet zijn bedoeld.^[12]:23

Onder andere de architect Jan Jacob Weve, die in 1910-1911 gedetailleerd archeologisch onderzoek op het Valkhofterrein verrichtte, meende dat het palacium publicum in de oorkonde uit 777 niet de toen nieuwe palts van Karel de Grote zou zijn bedoeld, maar een nog ouder paleis uit de Merovingische tijd.^[12]:24

Een andere vroege vermelding van de palts is afkomstig van Karel de Grotes persoonlijke biograaf, Einhard. Hij schrijft in zijn Vita Karoli Magni:

[...] Inchoavit et palatia operis egregii, unum haud longe a Mogontiaco civitate, iuxta villam cui vocabulum Ingilenheim, alterum Noviomagi super Vahalem fluvium, qui Batavorum insulam a parte meridiana praeterfluit [...] (vertaling: "Hij bouwde ook twee prachtige paltsen, één die weliswaar niet zo groot is als die in de stad Mainz, maar wel net zoals in Ingelheim en de andere te Noviomagus [Nijmegen] aan de rivier de Vahalis [Waal], die aan de zuidelijke kant langs het eiland der Bataven stroomt [...]")^{[13][14][12]:24-25}

De palts wordt ruim een eeuw later beschreven en geroemd door onder meer Regino van Prüm ("een geweldig groot en uitzonderlijk gebouw"), in diens kroniek uit 908. In 1080 wordt de palts opnieuw genoemd door Lambert van Hersfeld ("uitzonderlijk, zonder weerga").

De palts diende voornamelijk als adellijke residentie en tot op zekere hoogte als bestuurscentrum (villa regia). Er moeten aparte bijgebouwen zijn geweest voor het hofpersoneel en hier gelegerde militairen. Er zou plaats moeten zijn geweest voor enkele honderden personen.^[16] Uit beschrijvingen van Godfried van Viterbo blijkt dat er een gaanderij (aula columpnata) was (net als in het paleis in Aken).^[15]:23

Karel de Grote moet hier in ieder geval zelf zijn geweest in het voorjaar van 777, tijdens de viering van Pasen.^[17] In de Frankische annalen wordt dit bezoek vermeld meteen na dat van Kerstmis 776; het registreren van de bezoeken lijkt dus erg selectief te zijn gedaan.^[7]:81 Vanaf 804 zou hij (inmiddels keizer) de palts wat vaker hebben bezocht, voornamelijk rond de Paastijd.^[12]:25 Hij was er driemaal tijdens de laatste tien jaar van zijn leven en er – volgens de vermeldingen – daarvoor alleen in 777. Dit wordt gezien als een aanwijzing dat de palts aan het Valkhof pas vanaf 804 min of meer voltooid was.^[7]:84 In 806 liet Karel de Grote er de verdeling van zijn rijk tussen zijn drie zonen Karel, Lodewijk en Pepijn bezweren. In 808 zou hij nog een keer aan het Valkhof zijn geweest.^[17] De palts in Nijmegen was volgens sommige historici hoe dan ook "Karel de Grotes meest geliefkoosde verblijfplaats, na Aken".^{[18] :6} Er is ook nog een verband gesuggereerd tussen Karel de Grotes bezoeken aan het Valkhof en de kerstening van de Friezen.^[15]:21-22.^[5]

Lodewijk de Vrome zou hier in 815 de Vastentijd hebben doorgebracht.^[19] Enkele bronnen vermelden dat een houten zuilengang van de palts het begaf op een Witte Donderdag terwijl Lodewijk de Vrome aanwezig was.^[12]:24-25 Ook zou hij er in totaal zes keer een landdag gehad hebben. In 827 voerde hij hier bovendien vredesbesprekingen met de Deense koning Horik I; blijkbaar met weinig succes, want elf jaar later volgde een aanval door Deense Vikingen.^[18]:7 De Annales Bertiniani melden dat er in de herfst van 830 een grootschalig beraad werd gehouden, bijeengeroepen door Lodewijk de Vrome, om te proberen een revolutie tegen de keizer en diens vrouw te bezweren.^[1][7]:91

De Annales Xantenses maken reeds melding van een Noviomagum-Castrum in 846. Deze versterking valt echter niet logisch in verband te brengen met de plunderingen door de Noormannen, die enkele decennia later zijn begonnen.^[15]:24

In 870 sloot keizer Karel de Kale nog een verdrag met Rorik. De Vikingen namen echter rond 880 – of misschien al iets eerder – de palts in, nadat ze eerst een plundertocht langs de Rijn hadden gehouden.^[20] Vermoedelijk stonden ze toen onder leiding van Rorik en/of Godfried Haraldson junior.^[21][16] Ze gebruikten de palts hierna zelf als winterverblijfplaats tijdens een belegering door Lodewijk de Jongere, waarbij ze zelf een extra wal aanlegden en misschien ook een of meer grachten van het Romeinse castellum opnieuw uitgroeven en het terrein met houten palissades afschermden. Bij hun vertrek het jaar daarop (waarvoor ze losgeld betaalden) staken de Noormannen de palts in brand. De schade aan het bouwwerk lijkt toen beperkt te zijn gebleven en de palts moet niet lang daarna zijn herbouwd, nu veel meer als een echte vesting.^{[15]:25[22][19]}

Aan de oostelijke Waalkade, ten noorden van de laat-Romeinse keermuur, zijn brandsporen teruggevonden. Deze sporen zijn (echter zonder volledige zekerheid) toegeschreven aan de hiervoor genoemde gebeurtenissen. Het hier in de nabijheid gevonden aardewerk lijkt eveneens laat-Karolingisch.

In of nabij de palts is vermoedelijk omstreeks 1030 de Sint-Nicolaaskapel gebouwd. De Karolingische paltskerk in Aken lijkt hier duidelijk als voorbeeld te zijn genomen.^{[30][31][32][33]}

Lange tijd is als vanzelfsprekend aangenomen dat deze kapel ongeveer tegelijk met de rest van de palts was gebouwd en hiervan in eerste instantie onderdeel had uitgemaakt; vandaar de benaming Karolingische kapel.^[34][35] Volgens de bijgestelde inzichten vertoont de kern van de Nicolaaskapel echter geen duidelijke Karolingische kenmerken. Omstreeks 1910 stelde J.J. Weve vast dat de kapel zeer waarschijnlijk op z'n vroegst uit het midden van de 10e eeuw dateerde.^[36]:43 De kapel is later meermaals opnieuw onderzocht, en wordt nu nòg ongeveer een eeuw jonger geschat.

In 1047 is de palts opnieuw verwoest, tijdens een grote opstand tegen keizer Hendrik III onder leiding van Godfried II van Opper-Lotharingen.^{[24]: 237-239} De schade moet hierbij groter zijn geweest dan in 881. Van de toen pas gebouwde Nicolaaskapel zou alleen de bovenbouw zijn beschadigd.^[37]

Over de eerste tijd hierna is zeer weinig duidelijk. Vaak is uitgegaan van het idee dat de palts alleen gedeeltelijk was beschadigd, en mogelijk (deels) zelfs in gebruik bleef voor koninklijke en keizerlijke bezoeken. Keizer Hendrik IV zou in 1075 nog aan het Valkhof zijn geweest.^[18]:10

Omstreeks 1155 verrees aan het Valkhof de burcht van keizer Frederik I Barbarossa, die doorgaans geheel met de 8e-eeuwse palts wordt vereenzelvigd als herbouwing daarvan.^{[39][18]:10-11[40][16][41][29]:96-99[noten 1]} Een passage uit de Gesta Friderici Imperatoris, die ten tijde van, of net na de voltooiing van de Valkhofburcht moet zijn geschreven door Rahewin (leerling van Otto van Freising, de oom van keizer Barbarossa), is hierover zeer duidelijk:

[...] De zeer fraaie paleizen, eens door Karel de Grote in prachtige vorm opgebouwd als koninklijke residenties, bij Nijmegen en bij de villa Ingelheim [..] herstelde hij op passende wijze, en toonde hierbij zijn aangeboren grootsheid van geest.^[42][4]:42