Området har varit bebott sedan stenåldern. Vid flera ställen grävdes rester av boplatser från cirka 2000 f.Kr. fram. Ännu äldre fynd räknas till Butmir kulturen som hade ett unikt krukmakeri.[1]

En stad växte dock fram först på medeltiden. Staden hade länge endast ett fåtal invånare, som levde runt det centrala torg, kallat Tornjak, vilket tjänade som handelsplats. Det var en del av det dåtida Bosniens centrum, Vrhbosna.

När Bosnien senare blev en del av Osmanska riket kom Isa-beg Isakovic (som redan hade grundat staden Novi Pazar i dagens Sandžak) till Sarajevo och byggde en moské. Han lät även uppföra en byggnad för militära enheter och för administrationen (saraj).[2] I Isa-begs vakufnama beskrevs platsen. Eftersom man på den tiden uppförde områden runt moskéer tror man [vem?] att en liten kasaba började växa fram på platsen i mitten av 1400-talet. Namnet Sarajevo dokumenterades för första gången 1477 i en arabisk urkund.[2] Området växte mycket på grund av sin förmånliga försvarsposition. Bland annat uppfördes ett av Europas första vattenverk i staden. Snart byggdes fler moskéer och även en ortodox kyrka. Handeln tog fart och staden fick även tillgång till dricksvattenkranar; flera skolor startades och fattighus öppnades; muslimska tekijas byggdes och en carsija ("stadscentrum") växte fram. Allt fler invånare flyttade in och flera mahalas ("bostadsplatser") växte fram i utkanterna av staden med små gator, en moské och flera hus. Husen hade oftast, enligt den orientaliska traditionen, två trädgårdar; en manlig och en kvinnlig. Den manliga var vänd mot gatan och mer gjord för gäster medan den kvinnliga var vänd mot insidan och mer gjord för kvinnorna, barnen och allmänna familjetraditioner.

Majoriteten av stadens invånare var bosniaker (bosniska muslimer), med minoriteter av turkar och judar (det fanns även en synagoga i staden). Eftersom områdets kärna var de vackra sarajerna ("slotten") fick staden namnet Sarajevo ("slottets stad").

Sarajevo växte och expanderade till att bli Bosniens största stad och blev därför det bosniska ejaletets (administrativt område inom det osmanska riket) huvudstad. Där bodde den bosniske guvernören och flera rika bejer och paschor. En av de mest kända var Gazi-Husrev-beg, son till en bosniak från Trebinje och den osmanske sultanens dotter, som var en av de främsta krigarna i Osmanska riket. I Sarajevo bosatte han sig och öppnade en skola (Gazi-Husrev-begova medresa). Senare byggde han Sarajevos kanske ståtligaste moské (Gazi-Husrev-begova dzamija) och byggde även en bezistan (Gazi-Husrev-begov bezistan), ett klocktorn (sahat-kula) och öppnade mellan 80 och 200 affärer samt ett bibliotek (Gazi-Husrev-begova biblioteka).

Den turkiske reseförfattaren Evliya Çelebi beskrev Sarajevo. Många besökare beskrev staden som Balkans juvel och en vacker orientalisk seher ("njutningsplats"). Under dess glanstid hade staden 120 moskéer, flera ortodoxa kyrkor, en synagoga och cirka 169 dricksvattenkranar.

Sarajevo utsattes 1697 för en österrikisk attack under ledning av Eugen av Savojen där staden nästan helt brändes ner; den byggdes dock upp igen.[2] Flera bränder drabbade staden under årens lopp.

På 1700- och 1800-talen skedde flera bosniska uppror mot osmanerna, varav de flesta slogs ner brutalt.[2] Efter att sultanen beslutat att överlämna Bosnien till Österrike-Ungern och därmed drog tillbaka sina styrkor blev Sarajevo det återigen självständiga Bosniens huvudstad. När Österrike-Ungern anföll med ungefär 200 000 soldater blev Sarajevo en av de viktigaste punkterna för den bosniska armén, på ungefär 80 000 soldater. Efter ett utdraget krig förstärkte Österrike armén med 100 000 soldater och erövrade så småningom landet.

Sarajevo blev återigen erkänt som huvudstad för Bosnien och Hercegovina. Ett stadshus byggdes upp och tillsammans med flera bredare gator, en katolsk katedral, stadsbelysning, järnväg, nya stadsdelar samt en spårvagnslinje med mera.

Den 28 juni 1914 mördades den österrikiske kronprinsen Franz Ferdinand och hans maka Sophie av Gavrilo Princip i staden, i en händelse som kallas skotten i Sarajevo och som blev starten på första världskriget.[3] Sarajevo klarade sig väl undan kriget. När kriget var slut 1918 blev Bosnien och Hercegovina en del av det sydslaviska rike som senare kom att heta kungariket Jugoslavien.

I april 1941 ockuperades staden av tyska och kroatiska styrkor (se ustaša). Staden fritogs den 6 april 1945 av Titos partisaner och blev en del av det nya kommunistiska Jugoslavien där den blev huvudstad i den bosniska delrepubliken.[4] Staden fick flera nya gator och en ny järnväg, nya stadsdelar och flera fabriker och annan industri; bilar och andra fordon ökade drastiskt och staden fick flera nya byggnader och blev en modern europeisk huvudstad där flera kulturer möttes.[5]

Staden delades in i flera delar: den gamla delen med Bascarsija och de gamla orientaliska delarna, den centrala delen med Marijin dvor där regeringshuset och stadens största gata fanns, den nya delen med Hrasno, Grbavica med mera, samt den nyaste delen med Mojmilo, Saraj polje och så vidare. Av Sarajevos befolkning var vid denna tid de flesta bosniaker med mindre grupper serber, kroater, albaner och romer.

Mellan 8 och 19 februari 1984 arrangerades de olympiska vinterspelen i staden. Alla sportanläggningar var redan ett år innan färdigställda. Den första snön föll först ett fåtal dagar före tävlingarna. På grund av starka vindar skedde många omställningar i programmet. Med 1272 atleter från 45 nationer förtäckande Sarajevo ett nytt rekord för olympiska vinterspelen.[6]

1992 blev Sarajevo huvudstad i den nu självständiga republiken Bosnien och Hercegovina. Den serbiskkontrollerade jugoslaviska armén i Bosnien överlämnade då sina vapen till den nybildade bosnienserbiska armén (då dessa ville införliva delar av Bosnien i Serbien). Man hade redan före Bosnien-Hercegovinas självständighetsförklaring bott i bergen runt Sarajevo och belägrade nu staden helt. Befolkningen organiserade massiva protester för fred i början av april 1992. Trots de omfattande fredliga demonstrationerna var kriget ett faktum när den bosnienserbiska armén sköt mot demonstranterna och dödade Suada Dilberović och Olga Sučić. Dessa två kvinnor blev de första sarajevoborna som föll offer för kriget. Kort tid därefter skar bosnienserbiska styrkor av tillförseln av mat och förnödenheter till staden och lät stänga av dess elektricitet. Bosnienserbiska armén hade tillgång till mycket tyngre vapen än stadens försvarare, som främst bestod av dess invånare, muslimska poliser samt de så kallade gröna baskrarna (se Bosniska armén). Stadens försvarare lyckades ändå hålla belägrarna stången från stadens centrum. 10 000 Sarajevobor dödades, varav 1621 barn upp till 14 år (se Belägringen av Sarajevo). Efter fyra års belägring skrevs ett fredsavtal under. Bosnienserberna lämnade sina historiska delar av staden, Grbavica och bergen runt Sarajevo men behöll en del som fick namnet Istočno Sarajevo, "östra Sarajevo". Sarajevo har återuppbyggts efter kriget, och är den snabbast växande staden i Bosnien och Hercegovina.[källa behövs]