During the Ottoman rule, 13 bridges were built in Sarajevo. One of the most impressive ones is Šeher Ćehaja Bridge. The only written document indicating the year of the erection of the bridge is transcript of the chronogram in Mostar indicating it was built in 994 AH (1585/1586 CE). According to the source, the bridge was constructed by a man named "Alija known as Hafizadić".
The Šeher Ćehaja Bridge was destroyed a couple of times during its existence. It happened during the huge floods of 1619 and 1629 as well as in 1843 when the Miljacka River destroyed two pillars during repairs by Mustafa-paša. The bridge was again damaged in 1880.