O ovom mostu, vremenu gradnje, graditelju i osnivaču u izvorima i literaturi se malo zna. Iz samog imena mosta može se zaključiti da ga je podigao ili nanovo sagradio (obnovio) neki od sarajevskih šeher-ćehaja.
Prvi most na Miljacki sagrađen u osmanskom periodu je Careva ćuprija. Međutim to nije i najstarije mjesto prelaza preko rijeke. Naime, selo Brodac, (toponim šire lokacije na kojoj se nalazi Šeher – ćehajin most), moralo je dobiti ime po brodu-gazu preko rijeke, a on se mogao nalaziti upravo na mjestu na kojem je kasnije sagraden Šeher-ćehajina ćuprija. Dakle, pored mosta, samo mjesto na kojem je most sagrađen ima značaj historijskog mjesta.
Jedna od legendi koje se odnose na ovaj most upućuje na to da ga je podigao Hadži Husein. Legenda kaže da je 1610. godine u Sarajevu živio “čuveni Hadži Husein Hodžić, koji bijaše šeher-ćehaja, tj. upravitelj grada. Hadži Husein imadaše sina Mustafu, dobrog trgovca. Jednom prilikom ode Mustafa trgovačkim poslom u Stambol. Zagleda se u kćerku carskog terzibaše i sasvim se nastani u Stambolu. Pošto Mustafin otac ne imađaše više djece i ostao sam, naumi ostaviti svoj spomen, pa započe graditi jedan hair – kamenitu ćupriju preko Miljacke, koja se još i danas naziva Šeherćehajinom ćuprijom”. Most nije uspio završiti, jer je uskoro umro, pa je gradnja obustavljena. Kada je za to čuo njegov sin, vraća se u Sarajevo i završava gradnju mosta. Dalje legenda govori o tome da mu je ubrzo umrla i žena koju ukopa na Alifakovcu, gdje podiže turbe za nju i za sebe.
Stanje u kome se objekat nalazio u trenutku kada je započeta izrada projektne dokumentacije, te neospornu vrijednost ovog kulturnog dobra, već u fazi istraživanja, upućivali su na to da se radi o izvanredno složenom zadatku, kako s konzervatorskog, tako i s konstruktivnog aspekta. Izrada Izvedbenog projekta sanacije, rekonstrukcije, restauracije i konzervacije Šeher – ćehajinog mosta, započela je u decembru 1998. g. i trajala četiri mjeseca. Projekat je kompletiran početkom aprila 1999.g., kao cjelina koja se sastoji od dvije faze: konstruktivne (Projekat konstruktivne sanacije, projektant: Prof.dr. Zlatko Langof, d.i.g.) i konzervatorske (Projekat konzervatorsko – restauratorskih radova i radova rekonstrukcije, projektant: Nermina Mujezinović, d.i.a.). Rad na tehničkoj dokumentaciji sadržao je sljedeće segmente:
- Nulta faza: Istraživački radovi
- Prva faza: Izrada projekta konzervatorsko – restauratorskih radova
- Druga faza: Izrada Projekta konstruktivne sanacije
- Treća faza: Radovi na ispitivanju i valorizaciji materijala predviđenih za ugradnju pri restauraciji i rekonstrukciji uništenih i oštećenih elemenata.
Prilikom izrade Glavnog projekta, konsultirani su eksperti najrazličitijih stručnih profila. Terenska istraživanja vršile su za to usko specijalizirane ustanove. Realizacija je podijeljena na tri faze:
Pripremna faza podrazumijevala je radove rušenja i demontaže naknadno dodatih elemenata: konzolno izbačenih pješačkih staza, podužnih i poprečnih čeličnih traverzi i kolovoznog stroja kocke i asfalta, te prekid infrastrukturnih vodova koji su prelazili preko objekta. U ovom periodu, vršeni su i istražni radovi različitog karaktera.
U sklopu Prve faze, realiziran je čitav niz konstruktivnih i drugih zahvata, kao što su: sanacija temelja, riječnih stupova, tri svoda s gornje strane, preziđivanje četvrtog svoda (do Vijećnice); sanacija i rekonstrukcija dijelova čeonih i krilnih zidova; rješavanje problema odvodnje i zaštite kamenih elemenata. Ovi radovi okončani su u novembru 1999. g.
U okviru Druge – završne faze koja je u toku, predviđeno je okončanje intervencija usmjerenih ka vraćanju autentičnog izgleda objektu kroz restauraciju i rekonstrukciju oštećenih i nestalih originalnih elemenata, te konzervatorske radove na očuvanim originalnim dijelovima. Radi se o rekonstrukciji vijenca, ograde – korkaluka, hodne površine – “kaldrme” i slojeva podloge ispod nje, vraćanju originalne nivelete mosta i konzervatorskim zahvatima na fasadi. Ovo, također, pretpostavlja određene intervencije na neposrednom okruženju – uređenje samog prilaza mostu s lijeve i desne obale.
Onovljeni Šeher-ćehajin most svečano je pušten u promet 19. decembra 2001. godine.