Ennen 1100-lukua Châteauneuf-de-Randonia hallitsivat Barcelonan kreivit. Yksi heistä, Raymond Bérenger, antoi sen läänityksenä veljeksille Guarin ja Odilon vuonna 1126, joiden jälkeläiset myöhemmin perustivat Mercoiren luostarin (1187–1223). Myöhemmin eräs alueen herroista joutui kiivaaseen riitaan Menden piispan Guillaume de Peyren kanssa, joka syytti tätä alustalaistensa eli talonpoikien sortamisesta.
Guillaume valtasi hänen maansa ja pakotti hänet pyytämään rauhaa. Odilon Guarin alistui kuningas Ludvig VIII:lle vuonna 1226. Vuosina 1233–1243 Randonin herrat, jotka olivat avoimessa sodassa Polignac-suvun kanssa, päätyivät heidän liittolaisikseen Puy-en-Velayn piispan Bernard de Montaignen välityksellä ja sulautuivat lopulta kokonaan tähän sukuun.
Châteauneuf-de-Randonista, josta oli tullut yksi Gévaudanin tärkeimmistä linnoituksista, joutui vuonna 1361 suurten palkkasoturijoukkojen (Grandes Compagnies) valtaan. Yksi niiden johtajista, gaskonjelainen ritari Séguin de Badifol, ryösteli maaseutua 3 000 miehen voimin. Kaksikymmentä vuotta myöhemmin, vuonna 1380, toiset joukot valtasivat sen. Nämä puoliksi englantilaiset ja puoliksi gaskonjelaiset palkkasoturit olivat hyödyntäneet Ranskan ja Englannin välistä sotaa asettuakseen useisiin linnoituksiin Auvergnessa ja Languedocissa.
Mutta Randonin linna on erityisen kuuluisa siitä piirityksestä, jota englantilaiset kävivät siellä samana vuonna Bertrand Du Guesclinia vastaan. "Messire Bertrand", toteaa Froissart, "vannoi, ettei hän koskaan poistuisi sieltä ennen kuin olisi vallannut linnan; mutta sairaus iski häneen ja vei hänet vuoteenomaksi. Piiritystä ei kuitenkaan lopetettu, ja hänen miehensä taistelivat entistäkin kiivaammin".
Tuntiessaan loppunsa lähestyvän, Du Guesclin syleili ympärillään olevia vanhoja kapteeneja ja kehotti heitä kuolinvuoteellaan muistamaan, että missä tahansa he sotivatkin, papisto, naiset, lapset ja köyhä kansa eivät olleet heidän vihollisiaan; hän kuoli seuraavana päivänä. Samaan aikaan englantilainen kuvernööri oli luvannut antautua viidentoista päivän kuluessa, ellei saisi apujoukkoja. Sancerren marsalkka saapui piiritetyn kaupungin vallihaudalle ja vaati kuvernööriä luovuttamaan paikan: tämä vastasi antaneensa sanansa Du Guesclinille ja antautuvansa vain hänelle.
Tällöin Sancerre myönsi, ettei konstaapeli ollut enää elossa. "Hyvä on", vastasi kuvernööri, "vien kaupungin avaimet hänen haudalleen." Sancerre palasi valmistelemaan tätä poikkeuksellista seremoniaa. Sankarin teltasta poistettiin kaikki synkkä: hänen arkkunsa asetettiin kukilla peitetylle pöydälle. Pian Châteauneuf-de-Randonin kuvernöörin nähtiin poistuvan linnoituksesta varuskuntansa kärjessä. Hän kulki ranskalaisten leirin halki trumpettien soidessa ja saapui Du Guesclinin teltaan, jonne armeijan ylimmät upseerit olivat kokoontuneet seisten ja vaiti. Kuvernööri polvistui konstaapelin ruumiin eteen ja laski avaimet hänen arkulleen.
Tähän kertomukseen, jota historioitsijat ovat usein kaunistelleet, lisäämme kaksi otetta Du Guesclinin kronikasta, jonka on julkaissut Francisque Michel:
"Messire Bertrand ei viipynyt kauan Pariisissa; mutta kuninkaan suostumuksella hän kokosi suuren armeijan, astui Guyennen herttuakuntaan ja ratsasti vallaten kaupunkeja ja linnoja, kunnes saapui Châteauneuf-de-Randonin edustalle. Englantilaiset vartioivat linnaa, ja se oli runsaasti varustettu elintarvikkeilla ja tykistöllä. Linna oli vahva ja sijaitsi hyvällä paikalla. Messire Bertrand piiritti sitä ja teki useita hyökkäyksiä, mutta saavutti vain vähän".
"Messire Bertrand vannoi jatkavansa piiritystä ja ahdisti englantilaisia niin ankarasti, etteivät he saaneet mistään elintarvikkeita. Siksi englantilaiset pyysivät yhden päivän aselepoa ja lähettivät kapteeninsa messire Bertrandin luo neuvottelemaan. He lupasivat antautua tiettynä päivänä, elleivät saisi apua Englannin kuninkaalta, ja antoivat panttivankeja messire Bertrandille. Tämän vuoksi heille myönnettiin aselepo siihen päivään asti, jolloin heidän oli määrä luovuttaa linna".
"Aselevon aikana, jonka englantilaiset olivat pyytäneet Châteauneuf-de-Randonin luovuttamista varten, piiritystä johtanut messire Bertrand sairastui kuolettavasti. Nähdessään kuoleman lähestyvän hän vastaanotti hurskaasti sakramentit ja kutsui luokseen Sancerren marsalkan, jota hän piti erinomaisena ritarina, sekä messire Olivier de Maunyn ja leirinsä ritariston, joille hän sanoi: 'Herrat, minun on pian poistuttava seurastanne kuoleman vuoksi, joka on yhteinen meille kaikille. Teidän urheutenne, eikä omani, ansiosta onni on pitänyt minua suuressa kunniassa koko Ranskassa elinaikanani. Teille kuuluu se kunnia, ja teidän haltuunne uskon sieluni'".
"'Totisesti, herrat, minulla oli vakaa aikomus teidän urheutenne avulla päättää nopeasti Ranskan sodat ja palauttaa koko valtakunta kuningas Charlesin alaisuuteen; mutta en voi enää pysyä seurassanne. Rukoilen kuitenkin Jumalaa, Luojaani, antamaan teille aina rohkeutta kuningasta kohtaan; jotta teidän kauttanne, herra marsalkka, ja teidän sekä koko ritariston urheuden avulla – joka on aina palvellut häntä niin uskollisesti ja rohkeasti – hänen sotansa saataisiin päätökseen'".
"'Herra marsalkka ja te muut täällä olevat herrat, haluaisin pyytää teiltä yhtä asiaa, joka soisi sielulleni suuren rauhan, jos se vain on mahdollista. Ja sanon teille mikä se on: tiedätte, herrat, että englantilaiset ovat sopineet kanssani päivästä, jolloin he luovuttavat linnansa. Siksi toivon sydämestäni, että englantilaiset luovuttaisivat linnan ennen kuolemaani'".
"Messire Bertrandin sanat herättivät koko ritaristossa niin syvää sääliä ja surua, ettei sitä voi sanoin kuvata. He katsoivat toisiaan itkien, tuntiessaan sellaista surua jota ei koskaan aiemmin oltu nähty, ja sanoivat: 'Voi! Nyt menetämme hyvän isämme ja kapteenimme, paimenemme, joka ruokki meitä niin lempeästi ja johti meitä turvallisesti; ja jos meillä on rikkautta ja kunniaa, se on yksin hänen ansiotaan'".
"'Oi kunnia ja ritarillisuus, kuinka paljon menetätkään, kun tämä mies poistuu keskuudestamme!' Ja lukuisia muita valituksia kuultiin leiristä, jopa niin paljon, että linnoituksessa olijatkin huomasivat sen, vaikka eivät tienneetkään syytä. Niin päivä kului, eivätkä linnan puolustajat saaneet apua Englannin kuninkaalta".
"Seuraavana päivänä Sancerren marsalkka saapui linnan eteen ja kutsutti luokseen linnan kapteenin, joka saapuikin pian. Sancerren marsalkka sanoi hänelle ystävällisesti: 'Kapteeni ja ystävä, herra konstaapelin puolesta pyydän teitä luovuttamaan linnan ja sen avaimet sekä lunastamaan panttivankinne lupaustenne mukaisesti.' Kapteeni vastasi kohteliaasti: 'Herra, on totta, että meillä on sopimus messire Bertrandin kanssa, jonka tulemme pitämään kun näemme hänet, muttemme kenellekään muulle'".
"'Ystävä', sanoi marsalkka, 'jos en olisi tullut hänen puolestaan, en olisi tätä teiltä pyytänyt.' 'Totisesti, herra, pidän teitä luotettavana sanansaattajana. Neuvottelen sanoistanne varuskunnan tovereiden kanssa ja annan teille vastauksen, jos suvaitsette, lounaan jälkeen.' Tähän Louis de Sancerre suostui. Hän palasi messire Bertrandin luo ja kertoi hänelle englantilaisten vastauksen".
"Sitten messire Bertrand ymmärsi loppunsa olevan käsillä. Hän käski tuoda itselleen kuninkaallisen miekan, joka hänelle ojennettiin. Hän otti sen käteensä ja sanoi kaikille läsnäolijoille: 'Herrat, joiden seurassa olen saavuttanut maallista kunniaa ja urheutta, jonka arvoinen olen ollut, minun on nyt maksettava kuoleman velka, jolta kukaan ei voi välttyä'".
"'Ensimmäiseksi pyydän teitä rukoilemaan Jumalaa ja suosittelemaan hänelle sieluani. Ja te, Louis de Sancerre, joka olette Ranskan marsalkka ja olette ansainnut vieläkin suuremman kunnian, uskon haltuunne sieluni, vaimoni ja koko sukuni'".
"'Suositelkaa minua Ranskan kuningas Charlesille, suvereenille herralleni. Ja tämä miekka, jonka alaisuudessa Ranskaa hallitaan, palauttakaa se hänelle minun puolestani: sillä kenenkään muun uskollisempiin käsiin en voisi sitä antaa.' Näiden sanojen jälkeen hän teki ristinmerkin".
"Ja näin poistui tästä maailmasta urhea messire Bertrand Du Guesclin, jonka arvo hänen elinaikanaan oli niin suuri, että häntä kutsutaan uskollisuutensa ansiosta kymmenenneksi urhoolliseksi..."
Toisessa, Lancelotin käsikirjoituksessa, on seuraava kertomus, joka esittää uskottavamman version Châteauneuf-de-Randonin kuvernöörin ylistetystä käytöksestä:
"Messire Bertrandin kuoltua Ranskan joukoissa nousi suuri suruhuuto; tämän vuoksi englantilaiset kieltäytyivät luovuttamasta linnaa. Tällöin marsalkka Louis käski tuoda panttivangit vallihaudoille mestattaviksi. Nähdessään tämän englantilaiset laskivat välittömästi laskusiltansa, ja kapteeni tuli marsalkan luo tarjoten hänelle avaimia. Marsalkka kuitenkin kieltäytyi vastaanottamasta niitä ja sanoi hänelle:"
"'Ystävät, teillä on sopimus messire Bertrandin kanssa, ja teidän tulee luovuttaa ne hänelle.' — 'Jumala auttakoon! Herra', sanoi kapteeni, 'tiedätte hyvin, että messire Bertrand on kuollut, hän joka oli niin arvostettu, ja miten voisimme luovuttaa tämän linnan ja itsemme hänelle?' — 'Totisesti, herra marsalkka, te etsitte vain meidän häpeäämme vaatiessanne meitä antautumaan kuolleelle ritarille.' — 'Tästä emme enää neuvottele', sanoi marsalkka Louis, 'tehkää se heti: sillä jos jatkatte väittelyä, palatkaa linnaanne ja järjestäkää panttivankienne hautajaiset, sillä heidän elämänsä on pian ohi'".
"Englantilaiset ymmärsivät, ettei muuta vaihtoehtoa ollut. Niin he kaikki poistuivat linnasta kapteeni etunenässä, ja menivät marsalkka Louisin luo, joka vei heidät telttaan, jossa messire Bertrand lepäsi. Hän käski heidän luovuttaa avaimet ja asettaa ne messire Bertrandin arkulle, kaikkien itkiessä. Tiedettäköön, ettei paikalla ollut ainoatakaan ranskalaista tai englantilaista ritaria tai aseenkantajaa, joka ei olisi osoittanut syvää surua. Tällä tavoin päätti päivänsä messire Bertrand Du Guesclin, jota kaikki niin suuresti arvostivat".
"Châteauneuf-de-Randoniin marsalkka Louis jätti varuskunnaksi asemiehiä ja varsijousimiehiä. Sitten hän lähti suuren ritarisaattueen kanssa ja määräsi messire Bertrandin ruumiin palsamoitavaksi ja kuljetettavaksi haudattavaksi Bretagneen, Dinaniin..."
Mutta ennen Bretagneen saapumista hautajaiskulkue joutui kääntymään takaisin kuningas Charles V:n käskystä. Kuningas määräsi, että konstaapelin jäännökset oli haudattava Saint-Denisin kuninkaallisiin hautoihin. Le Puyn jakobiinikirkko oli säilyttänyt hänen sisälmyksensä; dominikaanit saivat hänen sydämensä.
Châteauneuf-de-Randon kuului Polignac-suvulle, ja se palautettiin heille. Mutta 1400-luvun alussa (1426) seikkailija nimeltä André Ribes hyödynsi Polignacien sisäistä perimysriitaa, valtasi linnan väkivalloin ja uskoi sen vartioinnin ryövärijoukolle, jonka johtajaksi hän oli noussut. Heidän avullaan hän ryösteli Beaucairen ja Toulousen voudinkuntia.
André Ribes otti itselleen Armagnacin äpärän arvonimen, vaikka hänellä ei ollut siihen mitään oikeutta. Häntä rohkaisi epäilemättä Armagnacin kreivin antama suojelu, sillä tämä tuki hänen rikollisia hankkeitaan.
Myöhemmin Claude-Armand de Polignac, joka oli raivoissaan isälleen François-Armandille – isä kun halusi pakottaa hänet kirkolliselle uralle jättääkseen omaisuutensa toisesta avioliitosta syntyneelle nuorelle Louisille – liittoutui kostoksi kalvinistien kanssa ja johti heidän joukkonsa oman sukunsa maille. Hän valtasi Châteauneuf-de-Randonin ja teki siitä itselleen tukikohdan, josta käsin hän ryösteli koko ympäristöä.
Gévaudanin säätykokouksessa Mendessä vuonna 1605 Polignacin kreivi, Randonin paronina, kiisteli etuoikeuksista Apcherin kreivin kanssa. Kun Apcherin kreivi voitti kiistan, Polignacin kreivin veli Villefort – luonteeltaan hyvin väkivaltainen mies – ei kyennyt sietämään tällaista loukkausta. Uskollisten miestensä avulla hän salamurhasi Apcherin kesken jumalanpalveluksen Menden kirkossa. Hän sovitti tämän rikoksen menettämällä päänsä Toulousessa.
Randonin linna tuhottiin Ludvig XIII:n hallituskaudella, kun maahan oli palautettu rauha. Vuoren juurella, jolla pieni kaupunki sijaitsee, kulkee tie Mendestä Puy-en-Velayhin. Juuri tämän tien varrelle, L'Habitarellen kylään, pystytettiin vuonna 1820 muistomerkki Du Guesclinille, oletettavasti sille paikalle, jossa hänen kuolintelttansa sijaitsi. Victor Adolphe Malte-Brunin teoksesta vuodelta 1882