Most je izgrađen u 16 vijeku. Natpis koji se nalazi u neposrednoj blizini mosta zasluge odaje Mehmed Paši Sokoloviću.


Pa ipak, prema lokalnoj legendi, most je izgradio pastir po imenu Muhamed. Jednoga dana on i njegov brat Sinan, dok su čuvali koze nedaleko od Jarčedola u jednoj pećini su pronašli blago. Podijelili su ga napola, od tog novca Muhamed je napravio most, a Sinan je na Bistriku izgradio džamiju koju narod zove Kecedžija ( Kec turska riječ za kozu). Bila ova priča istinita ili ne, most je bio na važnoj trgovačkoj ruti za Sandžak, Makedoniju i Istanbul i često je korišten sve do 19. vijeka.