Most u narodu poznat i kao Šeherija povezuje značajne gradske lokacije. Na jednoj strani nalazi se Vijećnica, a na drugoj Inat-kuća. Ovaj luk koji spaja dvije strane Miljacke sa sobom nosi i svoje legende.
Prva legenda kaže kako ga je podigao Hadži Husein, sarajevski šeher ćehaja (upravitelj grada). Smatra se da je po završetku izgradnje mosta Hadži Husein naredio da se u jedan od stubova ugradi dijamant. Dijamant je predstavljao izvor finansija za moguće popravke ćuprije. Jednog dana dijamant je nestao, ali krivca nije bilo teško naći, jer je Sarajevo tada brojalo oko 10.000 stanovnika. Pasvandžije (čuvari čaršije) tragali su za kradljivcem od kuće do kuće. Mufid Garibija, čuveni arhitekta kaže kako se na kraju pojavio jedan mladić koji je priznao da je ukrao dijamant. Zaljubio se u neku djevojku i poklonio joj ga. Tadašnji sarajevski kadija ganut ljubavlju mladih smilovao se i oslobodio mladića. Iako je dijamant vraćen, nikada više nije ugrađen u stub mosta.
Postoji i legenda o tome da je Hadži Husein htio izgraditi most kako bi ostavio spomen na sebe s obzirom na to da je njegov jedini potomak Mustafa, otišao poslom u Stambol, zaljubio se i zastalno nastanio tamo. Međutim, Husein umire prije završetka gradnje, te se prema šerijatu ona obustavlja. Mustafa se kući vratio tek kada je čuo da mu je otac umro gradeći ćupriju. Sa njim je u Sarajevo došla i terzibašina kćerka u koju se zaljubio. Mustafa je odlučio da će dovršiti gradnju ćuprije. Nedugo nakon toga, žena mu se razboljela i umrla, a sahranio je na Alifakovcu gdje je načinio turbe za oboje.
Legenda koja se također veže za ovaj most kaže kako je nekada postojao sluga koji se uvijek žalio svom gospodaru da je najveći baksuz na svijetu. Znajući da sluga svaki dan prelazi preko Šeher-ćehajine ćuprije, odlučio je ispitati njegovu tvrdnju. Prije nego što će sluga prijeći ćupriju, gospodar je postavio na sred mosta kesu s dukatima. Međutim, začudio se kada je sluga prošao pored kese nepogledavši je. Kada se sluga vratio, upita ga da li je na mostu vidio nešto neobično. Ovaj odgovori: “Toliko sam puta prešao preko njega da je nemoguće izbrojati. Neki dan spomenuh pred jaranima pa dodah kako bih ga zatvorenih očiju mogao preći, i to sve po sredini, da ne diram kamen na ogradi. Oni mi se nasmijaše, a ja danas odlučih da probam prije nego ih izazovem na opkladu. I, Boga mi, gazda prođoh žmireći, s kraja na kraj, a da se ogradi nisam primakao ni za pedalj. Vjerujte mi, sve po sredini”. “Baš po sredini”. Gospodar je tada bez razmišljanja potvrdio i rekao: „E, baš si baksuz“.
Vrijeme i sam graditelj mosta nisu precizno utvrđeni. Most je pretrpio mnoga oštećenja zahvaljujući poplavama (1619. i 1620., 1843., 1880. godine), ali svaki put je renoviran. Prilikom regulacije korita Miljacke, izgled mosta je promijenjen, pa je 1897. godine zatrpan jedan od pet lukova mosta na lijevoj obali Miljacke. Danas kada promatrate most, ne možete primijetiti da jedan luk nedostaje. 1904. godine skinuta je kamena ograda s mosta i dodati su pješački prelazi sa željeznom ogradom.
Šeher ćehajina ćuprija je najvjerovatnije sagrađena na mjestu gdje se za vrijeme Kraljevine Bosne nalazila skela za prijelaz.
Komisija o očuvanju nacionalnih spomenika je 25. do 31. januara 2005. godine proglasila Šeher-ćehajinu ćupriju nacionalnim spomenikom Bosne i Hercegovine.
Na Šeher ćehajinoj ćupriji je zapisano: “Alija koga nazivaju Hafizadićem u ime Boga podiže ovo dobro djelo”. Kad je ćuprija postavljena Hafizadić reče hronogramom: ‘Ovo je čudesan prijelaz”.