Indusketa arkeologikoek erakutsi dute antzinatik populatua izan dela Castle Rock, gutxienez Brontze edo Burdin Arotik hona.

K.o. 600 urteko Y Gododdin poema galestarrean Din Eidyn (Eidynen gotorlekua) aipatzen da baina gazteluaren benetako aipamena 1093koa da. Edinburgheko gaztelua Eskoziako garrantzitsuena bihurtu zen berehala eta David I.a Eskoziakoa (1124-1153) bertan bizi izan zen. Honek noble eta elizgizonen bilera egin zuen, Eskoziako parlamentuaren aurrekari kontsideratzen dena. Egurrezko gaztelua zen orduan, harrizko bi eraikin bazeuden arren, St Margaret kapera eta Andre Mariaren eliza.

1174ko Alnwickeko borrokan ingelesek Gilen I.a harrapatu zuten eta honek bere askatasunaren truke Edinburgheko gaztelua eman behar izan zien ingelesei. 1186an itzuli zioten gaztelua, Ermengarde de Beaumont printzesa ingelesarekin ezkondu zenean, eta berriz Eskoziako boterea bertan ezarri zen.

Eskoziako lehenengo independentzia gerran ingelesek gaztelua setiatu zuten eta hiru egunetako bonbaketaren ondoren eskoziarrek errenditu beharra izan zuten. 1300 urtean 325 soldadu ezarri zituzten bertan. 1307tik aurrera ingelesen boterea ahultzen hasi zen eta 1314ko martxoaren 14ko gauean Thomas Randolphek eraso azkar bat egin eta gaztelua eskoziarrentzat berreskuratu zuen. 1335ean ingelesek hartu zuten berriz gaztelua 1341ean William Dpuglasek berriz askatu zuen arte. 1357an Independentzia gerren amaiera etorri zen Berwickeko itunarekin.

XV mendean ere ingelesek setioak izan zituen. Garai hartan hainbat eraikin berri altxatu ziren Daviden dorrea, Koroaren enparantza, Errege familiaren apartamentuak eta Areto nagusia besteak beste. Armategi handi bat ere eraiki zen. Edinburgh hiria inguratu zuen harresi sendoa ere orduan eraiki zen. XVI mendean Errege familiak gero eta gehiago erabili zuen milia bateko distantziara zegoen Holyrood jauregia.

XVI mendearen bukaeran gerra zibila piztu zen Maria I.aren aldekoen eta haren seme Jakue VI.aren aldekoen artean. Maria I.aren aldekoak gazteluan zeuden Sir William Kirkcaldy of Grange-ren agindutara eta 1573ko urtarrilaren 1ean hiria bonbakatzeari ekin zioten Jakue I.aren aldekoek gaztelua setiatu zutenean. Hauek apirilean Sir William Drury-ren agindutara etorritako 1000 soldadu ingelesen laguntza jaso zuten. Castle Hill muinoan 27 kainoi ezarri zituzten eta maiatzaren 17an gaztelua bonbakatzeari ekin zioten. Maiatzaren 26an, akituta, Grangek gaztelua errenditu zuen eta 28an ingelesak sartu ziren barruan. 1603an Jakue VI.a Ingalaterrako errege bihurtu zen, Jakue I.a izenarekin.

Gazteluak kalte nabarmenak jasan zituen eta berreraiki beharra izan zuten. William MacDowall izan zen berreraikitze lanen arduraduna.

Jakue II.a Ingalaterrakoari Gilen III.a Orangekoak zuzenduriko noble talde batek 1688an Iraultza Loriatsua egin ondoren eskoziarrei errege berria onartzeko agindu zieten eta hauek ezezkoa ematean ingelesek Eskozia erasotu zuten. 7.000 soldaduk Edinburgheko gaztelua setiatu zuten. Barruan zeuden 160 soldaduk gogor eutsi zioten baina hiru hilabeteren ondoren 70 gizon galdu zituela ikusita Gordongo dukeak gaztelua errenditu zuen.

Borroka guzti hauen ondoren 1707an Eskoziak eta Ingalaterrak Batasunaren Ituna sinatu zuten. Highlandetako Jakobiten matxinadak izan ziren baina ez zuten arrakastarik izan.

Mendearen erdialdetik aurrera kartzela funtzioak hartu zituen gazteluak. Zazpi Urteko Gerra (1756–1763), Ameriketako Estatu Batuen Independentzia Gerra (1775–1783) eta Napoleondar Gerretan (1803–1815) izandako presoak gorde zituzten bertan. 1811ean ihesaldi handi bat gertatu zen eta 1814an kartzela izateari utzi zion.

Puntualki, Lehen eta Bigarren Mundu Gerratan ere gerra presoak izan ziren bertan. 1993an Antzinako Monumentu berezia izendatua izan zen eta 1995ean UNESCOk Gizateriaren Ondare izendatu zuen gainontzeko Edinburgheko alde zaharrarekin batera.