As an historic city, Sarajevo has numerous myths and folklore surrounding it as well. The character Nasrudin Hodza is popular throughout the former lands of the Ottoman Empire, and Sarajevo is no exception. Numerous stories about him dealing with Sarajevo have been written over the years. A famous piece of Sarajevo folklore is the story of the Sarajevo Orthodox Church. It was said that when a request came to build it, authorities required that it go no higher than the tallest minaret in Sarajevo. A wise old man was then said to have advised for the church to be built into the ground. Thus the building reached a proper height but met the restrictions.

Numerous other famous bits of Sarajevo folklore survive representing many different eras of Sarajevo's history. One of the earliest is the story of the Goat's Bridge. As the story goes, an old herder was tending his goats by the river Miljacka when one of them started ferociously digging at a certain spot of the ground. Mystified, he walked over for a closer look only to find numerous sacks of gold. With the gold, he then built a great bridge over the river that would for years be the main crossing for travelers on their way to Istanbul.

Far more recent is the story of Sarajevo's Romeo and Juliet. It is said that during the siege of sarajevo a young Serb boy and Bosniak girl decided to flee the city together. They got as far as no man's land before the boy was shot dead and the girl wounded. Rather than flee alone however, she turned to stay by her lover's side, where she too eventually died.