U osmanskoj administrativnoj podjeli, među gradovima u Bosni Travnik zauzima istaknuto mjesto, o čemu svjedoči i činjenica da je grad u dugom vremenskom periodu bio sjedište kadiluka a od 1699. do 1850. godine i Bosanskog pašaluka.
Prenos vezirske stolice povoljno je djelovao na razvoj ove do tada neznatne kasabe, što je ostavilo traga i u materijalnoj kulturi Travnika. Grad se proširio, izgrađene su nove mahale, povećan je priliv stanovništva, osnovana je nova Gornja čaršija. Razvila se trgovina i privreda i u to doba nastali brojni javni i privatni objekti.
Historija Šarene džamije vezana je za urbani razvoj grada i imena značajnih vakifa, od kojih su dva nosila vezirsku titulu.
Prvobitnu džamiju još krajem XVI vijeka izgradio je Gazi-aga koji je, prema zapisima, bio veliki junak i borac te pripadnik janjičara, po kojem je ona sve do 1757. godine bila poznata kao Gazi-agina džamija.
Nije sačuvan opis Gazi-agine džamije. Ova prva džamija je imala i harem koji je vremenom potiskivan i stiješnjen uz samu džamiju.
S obzirom na to da niko nije brinuo o održavanju džamije ona je vremenom propala i nakon 200 godina, 1757. godine, bosanski valija Sopa Salan Ćamil-Ahmed-paša iz temelja je obnovio Gazi-aginu džamiju, sagradivši pod njom bezistan sa dvadeset i sedam dućana, pa se ona od tada nazvala Ćamilija džamija.
Iz vakufname Ahmed-pašine, tj. vakufname Ćamilija džamije iz 1757. godine, saznaje se samo da je Gazi-agina džamija te godine bila u potpuno urušenom stanju, te da ju je nešto prije 3. jula 1757. godine obnovio dobrotvor Ahmed-paša.
Vakufnama sadrži podatke o tome da je džamija iz temelja obnovljena, osim kamene munare, i da je tada temeljito opravljen i vodovod. Tom prilikom je uz džamiju izgrađena i česma sa četiri lule i u nju dovedena voda iz već postojećeg vodovoda.
Ova vakufnama, pored drugih podataka, sadrži i opis nove građevine u kome se kaže da je džamija počivala na kratkim kamenim stupovima, te da je pod džamijom bezistan sa dva ulaza i deset dućana unutar njega i sedamdeset poredanih oko bezistana, iza arkada džamije. Tokom požara koji se dogodio 1815. godine džamija je uništena do temelja.
Nakon ovog požara džamiju je temeljito obnovio tadašnji bosanski vezir Skopljak Sulejman-paša, po kojem se džamija od tada naziva Sulejmanijom. Ovaj vezir je stolovao u Travniku od 27. oktobra 1815. do 23. januara 1818. godine.
Na desnoj stani džamije i danas stoji riječ na arapskom “Mašallah” a razlog toga prenosi se kao priča s koljena na koljeno.
Nakon što je Sulejman-paša izgradio džamiju pitao je da li neko ima primjedbu. Svi su šutjeli i ustručavali se da bilo šta kažu. Javila se jedna osoba koja je rekla: ‘Imam ja’ i svi su nju pogledali u čudu pitavši se kako smije išta reći paši koji je napravio džamiju, Tada je ta osoba rekla da fali jedan natpis ‘Mašallah’ u smislu pohvale. Prisutni su se nasmijali, a to je uklesano.
Obnovom iz 1815. godine, džamija je dobila današnji izgled, odnosno džamija je dobila zidne dekoraciju na fasadama i unutar objekta. Upravo po toj dekoraciji džamija je dobila naziv Šarena.
U austrougarskom periodu, nakon 1906. godine, dekoracija na fasadama i u unutrašnjosti je prekrečena, a potom je oslikana nanovo šablonskom ornamentikom.
Tokom savezničkog bombardovnja Travnika 1944. godine porušen je zapadni ugao objekta a već 1945. godine džamija je obnovljena.
Munara se nalazi na lijevoj umjesto na desnoj strani džamije kako je, inače, pravilo kod gradnje džamija. Jedna od teorija je da s desne strane džamije nije bio vakufski prostor pa nisu htjeli uzurpirati taj dio. Druga teorija je da s te desne strane teče potok i da konstrukcija munare ne bi izdržala. Desni dio džamije i danas ima blagi pad jer je Travnik napravljen nad vodom.
Džamija je potpuno obnovljena 2019. godine.
Šarena (Sulejmanija) džamija u Travniku proglašena je nacionalnim spomenikom Bosne i Hercegovine.