בשנת 1557 הורה הסולטאן סולימאן הראשון להחליף גשר עץ ישן ורעוע שניצב במקום. עבודות הקמת הגשר החלו באותה שנה, ולפי כתובת שנמצאה במקום נמשכו עד שנת 974 לספירה המוסלמית, היינו עד התקופה שבין יולי 1566 ליולי 1567. למעט עובדה זו ידוע שהגשר נבנה על ידי מימר היירודין, תלמידו של האדריכל העות'מאני הידוע סינאן וכי שני המגדלים שנצבים בשני צידיו קדמו לו. ממדיו של הגשר נחשבו ליוצאי דופן בתקופת הקמתו, ומקובל שהיה זה הגשר הגדול מסוגו באותה עת. אופן הקמת הפיגומים, הדרך שננקטה כדי לשמר את יציבותם משך שנות ההקמה הרבות, כמו גם דרך העברת חומרי הבניין מגדה לגדה, נותרו כולם בגדר תעלומה. הגשר ("Most") העניק את שמו לעיר, הוא מופיע על סמלה והפך במשך מאות שנים לסימן ההיכר שלה.

כמאה שנים לאחר הקמתו של הגשר החלו צעירי העיר לקפוץ מהגשר אל מימי הנרטבה. העדות הראשונה למנהג זה היא משנת 1664. בשנת 1968 לבש המנהג צורה של תחרות רשמית שהתקיימה מדי שנה בקיץ, וגם לאחר הריסתו של הגשר בשנת 1993, המשיכו התחרויות מפיגום שהוצב במקום בו הגשר ניצב.

במלחמת בוסניה, הן הסרבים והן הקרואטים ראו בגשר וברחובות העיר העתיקה שסביבו סמל בוסני-מוסלמי, ויירטו אותו באופן תדיר. בשנת 1992 נפגע הגשר מהפגזות של כוחות סרביים, וביום 9 בנובמבר 1993 בשעה 10:15 הרסו כוחות מועצת ההגנה הקרואטית (Hrvatsko vijeće obrane, HVO) את הגשר והפילוהו לנהר.

הגשר שוקם ונבנה שוב על ידי חברה טורקית תחת ניצוחו של ארגון אונסק"ו ובמימון בינלאומי, בעיקר של ממשלת לוקסמבורג. 1,088 האבנים ששימשו לבנייה המחודשת, עוצבו בהתאם לטכניקה המקורית, ועלות ההקמה עמדה על 12 מיליון אירו. הגשר נפתח מחדש בטקס חגיגי ביום 23 ביולי 2004, ובשנת 2005 הוא הוכלל, יחד עם הרחובות הסמוכים לו ומספר מבני ציבור עתיקים נוספים, ברשימת אתרי המורשת העולמית של אונסק"ו. הגשר שב להיות סמלה של העיר והכללתו ברשימת אתרי המורשת העולמית העניקה עידוד של ממש לענף התיירות בעיר שהיא המתוירת במדינה.