Okolice dzisiejszego Sarajewa zamieszkane były już w czasach prehistorycznych. W Butmirze, obecnie przedmieściu Sarajewa, w latach 1893–1896 odsłonięto ślady osad z okresu neolitycznego sprzed ok. 4500 lat. Tereny te były również zamieszkane w czasach rzymskich (rzymska osada na terenie dzielnicy Ilidża).

W średniowieczu w miejscu dzisiejszego Sarajewa istniała osada Vrhbosna. Nowożytne Sarajewo założone zostało w 1462 r. i znacznie rozbudowane przez pierwszego osmańskiego władcę Bośni Isa-beg Isakovicia. W okresie panowania tureckiego Sarajewo było centrum administracyjno-politycznym Bośni osmańskiej. W 1697 r., po spaleniu miasta przez wojska austriackie, stolicę przeniesiono do Travnika.

W 1878 r. Bośnia została zajęta przez Austro-Węgry. Pod rządami austriackimi Sarajewo zmodernizowano i znacznie rozbudowano.

28 czerwca 1914 r. w Sarajewie serbski nacjonalista, Gavrilo Princip, dokonał zamachu na austriackiego następcę tronu, arcyksięcia Ferdynanda. Wydarzenie to było bezpośrednią przyczyną wybuchu I wojny światowej.

Jesienią 1918 r. mjr Artur Ganczarski (legionista) utworzył w Sarajewie Legion Polski w sile 600 żołnierzy i 63 oficerów, który przyprowadził do Polski, do Krakowa w dniu 25 listopada 1918 r. Legion ten traktuje się jako część składową Armii Hallera.

Po I wojnie światowej, w Królestwie Serbów, Chorwatów i Słoweńców miasto było stolicą prowincji – Drińskiej banowiny.

Po II wojnie światowej Sarajewo zostało stolicą republiki Bośni i Hercegowiny. Rozwinęło się w ważne centrum handlowo-przemysłowe. Szczyt rozkwitu przypadł na lata osiemdziesiąte. W 1984 r. w Sarajewie odbyły się zimowe igrzyska olimpijskie.

Podczas wojny w Bośni, po rozpadzie Jugosławii, miasto było oblegane przez Bośniackich Serbów. Oblężenie rozpoczęło się 6 kwietnia 1992 r. i trwało do końca października 1995. Podczas oblężenia miasto było cały czas ostrzeliwane z otaczających gór, odcięte od dostaw wody i prądu, a żywność dostarczano nieregularnie. Zginęło ponad 10 500 osób, praktycznie wszystkie budynki zostały zniszczone lub uszkodzone. O walkach i związanych z nimi tragicznych dla mieszkańców skutkach opowiadają m.in. film dokumentalny Miss Sarajevo (1995), dramat wojenny Aleja snajperów (1997) i dramat społeczny Grbavica (2005). Powstały także piosenki „Miss Sarajevo”, opowiadająca o tragedii w tym mieście, autorstwa U2 i Luciano Pavarottiego oraz „Bosnia” zespołu The Cranberries. W latach 90. także w polskiej muzyce można było odnaleźć akcenty związane z sytuacją Sarajewa: punkowy zespół „Łysina Lenina” nagrał piosenkę o wspomnianych wydarzeniach pt. „Sarajewo”, a także zespół Balkan Electrique, piosenkę pt. „Sarajevo (Dimitrica II)”.

Od zakończenia wojny i zawarcia w listopadzie 1995 r. układu z Dayton, Sarajewo jest odbudowywane, głównie przy wsparciu finansowym Unii Europejskiej. Ślady wojny są jednak cały czas wyraźne, a tereny położone bezpośrednio wokół miasta są wciąż zaminowane.