Sarajevu 1461. gadā nodibināja pirmais osmaņu Bosnijas bejs (turku: bey) Isa Ishaka dēls (turku: İshakoğlu İsa Bey, bosniešu: Isa-Beg Ishaković), kurš uzcēla pirmo mošeju un Sarajeva kļuva par Bosnijas ejāleta administratīvo centru (1580—1583 un 1851—1864). Ejāleta centrs uz laiku tika pārcelts uz Baņa Luku (1583—1686) un Travniku (1686—1851).

1697. gadā Habsburgu karavadonis Savojas princis Eižens ieņēma un nodedzināja pilsētu.

1878. gadā Bosniju anektēja Austroungārija, un Sarajevā sāka attīstīties rūpniecība.

1914. gada 28. jūlijā Sarajevā atentātā tika nogalināts Austroungārijas troņmantinieks Francis Ferdinands, un tas kļuva par cēloni Pirmajam pasaules karam.

Starp pasaules kariem Sarajeva bija Drinas Banovinas provinces centrs Dienvidslāvijas sastāvā. Otrā pasaules kara laikā Sarajeva bija ustašu Horvātijas brīvvalsts sastāvā. Visi pilsētas ebreju iedzīvotāji tika iznīcināti. Pretošanās kustību vadīja leģendārs Tito kaujinieks ar segvārdu Valters.

Pēc Otrā pasaules kara Sarajeva kļuva par Bosnijas un Hercegovinas republikas Dienvidslāvijas sastāvā galvaspilsētu. Pilsēta ļoti strauji auga, un tika apbūvēta ar standarta dzīvojamiem kvartāliem. 1984. gadā Sarajevā notika ziemas olimpiskās spēles.

1990. gados, izceļoties Dienvidslāvijas kariem, 1992. gada 5. aprīlī pilsētu ielenca serbu militārie spēki. Sarajevu aizstāvēja bosniešu kaujinieki. Sākās kauja par Sarajevu, kura ar dažādu intensitāti turpinājās gandrīz četrus gadus. Pilsēta ciets no serbu armijas veiktās pilsētas bombardēšanas, kura notika no apkārtējiem kalniem, bet īpaši no snaiperu uzbrukumiem civiliedzīvotājiem, kuri spiesti regulāri iziet ielās pēc pārtikas un dzeramā ūdens.

Pamatojoties uz Deitonas līgumu, Sarajeva kļuva par neatkarīgās Bosnijas un Hercegovinas valsts galvaspilsētu. Līdz 2005. gadam ir novērsta lielākā daļa no kara postījumiem.