Az eredeti Nottingham-kastély 1067-ben épült az angliai Notthingamben Hódító Vilmos parancsára egy évvel azután, hogy a normannok győzedelmeskedtek a hastingsi csatában.
Az első normann erőd ekkor még csupán egy fából készült földhalomvár volt,
az építője pedig William Cavendish, Newcastle első hercege.
Az új angol király, Hódító Vilmos egy olyan vár építését rendelte meg tőle, amely a korabeli „lakótorony, földvár és várfal" stílust képviselte. A helyszínt gondosan választotta ki: a Castle Rock néven ismert, Nottingham városára néző sziklacsúcsot.
Ez a természetes, negyven méter magas fok a hegy délnyugati oldalán fekszik.
Akkoriban, a 11. század második felében jelentős királyi erődítménynek és alkalmi rezidenciának számított. A kastély végül évszázadokon keresztül Anglia egyik legfontosabb nemesi és uralkodói központjaként szolgált.
Körülbelül egy évszázaddal később, II. Henrik uralkodása alatt a javarészt fából készült kastélyt kővel bővítették, és így egy sokkal erősebb és jobban védhető kővárrá alakították át.
A legmagasabb pontjára helyezték át az úgynevezett felsővárat, ettől északra feküdt a királyi rezidenciáknak otthont adó középső várudvar, miközben a terület keleti részén egy hatalmas külső várudvar terült el.
Nem sokkal Henry halála után, 1194-ben történelmi csata zajlott a nottinghami várkastélyban.
Ez pontosan akkortájt történhetett, amikor Oroszlánszívű Richárd király az angol nemesek oldalán a keresztes háborúban harcolt. A vár közben János herceg támogatói – többek között a legendából jól ismert Robin Hood egyik legnagyobb ellensége, Nottinghamshire sheriffje – kezére jutott.
Ekkor került sor a legenda szerint a két rivális közötti végső leszámolásra is.
Ami viszont a történelmi tényeket illeti: márciusban Oroszlánszívű Richárd hadjáratot indított János herceg felkelése ellen, aki a szentföldi csaták során megismert és a hadjárat során bevetett ostromgépek mintájára hasonló fegyvereket építtetett.
A királyt Chester grófja, Ranulph de Blondeville és Huntingdon grófja is segítette. Annak ellenére, hogy a várat korábban jócskán megerősítették, a várvédők néhány nap után megadták magukat.
A 14. században egy furcsa páros, Franciaországi Izabella angol királyné és annak szeretője, Roger Mortimer gróf élte mindennapjait a nemesi kastélyban. Mindketten régensként kormányozták az országot, miután Izabella férjét, a kis Eduárd (III. Eduárd) apját, II. Eduárdot a berkeley-i kastélyban, Gloucestershire-ben meggyilkolták.
1330. október 19-én, nem sokkal 18. születésnapja előtt III. Eduárd és néhány megbízható társa Sir William Montagu vezetésével
puccsot tervezett és hajtott végre a nottinghami várban anyja ellen.
Egy hozzájuk hű szolga, William Eland kísérte őket, aki ismert egy titkos alagutat a kastély alatt, amely az épület egyik magasabb pontjához vezetett.
A merénylők csapata sikeresen bejutott, megölték Mortimer testőreit, és átvették a hatalmat. Izabellát valamint Rogert elfogták és letartóztatták. Utóbbit megkötözve vezették ki az alagúton keresztül, majd a londoni Towerbe szállították.
Egy hónap múlva bíróság elé állították, elítélték, majd felakasztották. Izabellát azonban a fia megmentette, ám erőszakkal lemondatta, végül Rising várába száműzték, ahol csak sok évvel később, 1358-ban halt meg.
A szeretők eltávolítása után kezdődhetett meg Eduárd uralkodása.
A különös páros uralkodása után III. Eduárd berendezkedett a várban,
és hamarosan már az országgyűléseket is itt tartotta.
Nottingham kastélya ideiglenes börtönként is szolgált 1346-ban II. Dávid skót király számára, aki kiskorúként kezdte meg uralkodását apja, I. Róbert halála után.
Ezt próbálta meg a maga hasznára fordítani III. Eduárd, és bevonult Skóciába, ahol minden igyekezetével védencét, a Baliol családból való Eduárdot igyekezett trónra segíteni. Dávid ekkor elmenekült Franciaországba, ahol épp a százéves háború dúlt.
Francia segítséggel próbált visszajutni Skóciába, ám az angolok útközben elfogták,
foglyul ejtették, és bebörtönözték.
A trónra csak azzal a feltétellel kerülhetett vissza, hogy elfogadta Anglia fennhatóságát, és jelentős váltságdíjat is kellett fizetnie. Eduárd közben elkezdte bővíteni az épületkomplexumot: a középső várudvar nyugati oldalán új toronnyal, a Magastorony alatt pedig új börtönnel gyarapodott a vár. A munkálatokra több okból is szükség volt.
A vár közben ugyanis egyre rosszabb állapotba került: a nagyterem tetejének egy része beomlott, valamint az új épületrészek fa-, ólom- és üvegszerkezetei is pusztultak. A várkapitányok azonban hiába sürgették a felújítást.
A kastély királyi rezidenciának így csupán körülbelül 1600-ig volt használható;
az épület védelmi rendszerei hamarosan elavultnak bizonyultak.
Ráadásul 1640-ben kitört az angol forradalom, miközben az erőd már félig romokban állt.
A kastélyt 1642 augusztusában I. Károly ostromolta, aki itt gyűjtötte össze a csapatait.
Miután távozott, a várat elfoglalták a köztársaságpártiak, akik John Hutchinson ezredes vezetésével számos támadást visszavertek.
A királypártiak bukása után 1649. január 30-án I. Károlyt kivégezték. Hutchinson azt javasolta, hogy rombolják le a várat, hogy ezzel is megakadályozzák a háború során a használatát. Így 1651-ben Nottingham várának maradványai megsemmisültek. Mindazonáltal a középkori vár földalatti szerkezetei máig megmaradtak.
Az angol forradalom bukása után trónra került II. Károly azonban elrendelte a vár felújítását.
A jelenlegi hercegi palotát Henry Cavendish, Newcastle második hercege építtette 1674 és 1679 között.
Mintegy két évszázaddal később, 1831-ben a palotát lázadók gyújtották fel
(utána itt alakultak ki ugyanis a brit birodalom leghírhedtebb nyomornegyedei, és e telepek lakói lázadtak fel Newcastle hercege, Henry Pelham-Clinton ellen, aki nem volt hajlandó elfogadni az 1832. évi nagy reformtörvényt).
A tűzvész eredményeként csak a palota külső szerkezete maradt épen. A kastély ezután több mint negyven évig elhagyatottan állt egészen 1875-ig, amikor Thomas Chambers Hine felújíttatta.
Három évvel később újra megnyitották a közönség számára, de mint képzőművészeti múzeumot. Londont leszámítva ez volt az első városi művészeti galéria Nagy-Britanniában, amelyet értelemszerűen összekapcsoltak az olyan híres népi hősökkel, mint Robin Hood.