Edinburgo miesto teritorijoje randama daug priešistorinių radinių. Iki šios teritorijos nusausinimo čia buvo ežeringa ir pelkėta vietovė tarp kalvų, kurioje buvo išsidėsčiusios gyvenvietės. Per paskutiniuosius du šimtmečius čia buvo randami ir bronziniai radiniai. Caiystane View gatvėje link Oxgangs kelio stovi didelis menhyras (angl. Standing stone). Mezolito radiniai ir romėnų pilies likučiai yra Cramond kaime Edinburgo pakraštyje.

I m. e. a. pabaigoje Lodiane išsilaipino romėnai, kurie čia rado keltų-britų gentį votadinius. Kažkuriuo metu prieš VII a. Gododinas pastatė Din Eldyn arba Etin kalvos tvirtovę. IX a. pirmoje pusėje Nortumbriją ir Edinburgą nukariavo vikingai ir įtraukė į Danelagą. 910 m. danus nugalėjus Edvardui Vyresniajam miestą užėmė škotai. 1020 m. karalius Malkolmas II įtraukė Edinburgą į Škotijos karalystės sudėtį. 1093 m. Edinburge paminima tvirtovė, kuri išsivystė į šiuolaikinėje miesto panoramoje dominuojančią Edinburgo pilį. XII a. šalia Edinburgo pilies buvo nedidelis miestelis, o netoliese šalia Holyrood abatijos - gyvenvietė. XIII a. abi gyvenvietės tapo karališkąja valda. Tuo pačiu metu Edinburgas ir pasienio regionas tapo Anglijos ir Škotijos karalysčių ginčų objektu. Anglai nekartą apgulė ir užėmė miestą, tačiau per tolimesnius porą amžių škotai miestą išlaikė savo rankose.

Škotijos karalystės sudėtyje miestas vystėsi ekonomiškai ir kultūriškai. 1583 m. Edinburge įkurtas universitetas, kuris pagal įkūrimo senumą tėra ketvirtas Škotijoje, St Andrews universitetas buvo įkurtas dar 1450 m. Iš pradžių Albos karalystės (žr. Škotijos karalystė) sostinė buvo Scone (dab. Old Scone). Vėlyvaisiais viduramžiais ji prarado savo reikšmę ir jos vaidmenį perėmė 1,5 km aukščiau upe buvęs Pertas. Ir kiti laisvieji miestai (burghs) Škotijos istorijoje turėjo svarbų vaidmenį, pvz., Stirlingas. Viduramžiais sostinėje dažnai ir ilgą laiką lankydavosi karališkasis dvaras, kuris paprastai keliaudavo ir po kitas vietoves. 1603 m. Škotijos karalius Jokūbas I tapo pirmuoju Stiuartų dinastijos monarchu karūnuotu Anglijos karaliumi. Taip susidarė personalinė Škotijos ir Anglijos unija. Tais pačiais metais jis įkūrė Škotijos parlamentą, kurio pagrindinė būstinė buvo pagrindinėje Edinburgo gatvėje. Jokūbas I nusprendė perkelti sostinę iš Stirlingo į Holyrood dvarą taip faktiškai Edinburgas tapo Škotijos sostine.

1639 m. Edinburge kilo maištai nukreipti prieš anglikonų bažnyčios stiprinimą, kurie peraugo į visos Škotijos sukilimą ir Anglijos pilietinį karą. Oliveriui Kromveliui nugalėjus škotų kariuomenę miestą užėmė britai. Viena svarbiausių datų miesto ir visos Škotijos istorijoje yra 1707 m. gegužės 1 d. sudaryta unijos su Anglija sutartis - Act of Union. 1745 m. kilo Antrasis jakobitų sukilimas prieš Anglijos vyriausybę. Sukilėliai užėmė Edinburgą, bet po kelių pirmųjų laimėjimų buvo sumušti mūšyje prie Culloden. Po sukilimo numalšinimo britai ėmėsi represijų prieš škotus. Anglų viršenybės ženklan buvo nuspręsta įkurti naują kvartalą turtingai britų buržuazijai, pavadintą New Town. Šiauriau pilies sukurtas simetriškas plačių ir patogių gatvių tinklas, tarp kurių buvo statomi gyvenamieji namai, bankai ir ofisai. Naujojo kvartalo gatvių pavadinimai buvo skirti Anglijos karališkosios šeimos atstovų atminimui - pagrindinė gatvė pavadinta George Street karaliaus Jurgio III garbei, o jai paralelinės gatvės - Queen street ir Princess street jo žmonos Šarlotės ir sūnų garbei.