El pont original va substituir un pont penjant de fusta més antic de dubtosa estabilitat. La construcció començà el 1557 i va durar nou anys: segons la inscripció el pont s'acabà el 974 aH, corresponent al període comprès entre el 19 de juliol de 1566 [1] i el 7 de juliol de 1567. Poc se sap de la construcció del pont, que es creu que es feu amb morter fet amb clares d'ou,[1] i tot el que s'ha conservat per escrit són records i llegendes i el nom del constructor, Mimar Hayruddin. Carregat amb la pena de mort per construir un pont d'aquestes dimensions sense precedents, Hayruddin es va preparar per al seu propi funeral el dia en què finalment es van retirar les bastides de l'estructura acabada: era l'arc artificial més ampli del món.

L'explorador otomà del segle xvii Evliya Çelebi va escriure que el pont «és com un arc de Sant Martí que s'enlaira fins al cel, que s'estén d'un penya-segat a l'altre... Jo, pobre i miserable esclau d'Al·là, he passat per 16 països, però mai no he vist un pont tan alt. Es llança de roca en roca tan alt com el cel».[2]

A mesura que la importància econòmica i administrativa de Mostar creixia amb la presència del domini otomà, el precari pont penjant de fusta sobre el congost de Neretva va requerir una substitució. El vell pont del riu «... era de fusta i penjava de cadenes», escrigué el geògraf otomà Katip Çelebi, i «... es balancejava tant que la gent que el travessava ho feia amb por de morir». El 1566, Mimar Hayruddin va dissenyar un pont del qual es deia que costaria 300.000 drams (monedes de plata). El projecte de construcció de dos anys fou supervisat per Karagoz Mehmet Bey, gendre del sultà Solimà i patró del complex més important de la mesquita de Mostar, la mesquita Hadzi Mehmed Karadzozbeg.