Historija Sulejmanije (Šarene) džamije vezana je za urbani razvoj grada i imena značajnih vakifa, od kojih su dva nosila vezirsku titulu. Na mjestu Šarene džamije je još krajem XVI stoljeća podigao svoju džamiju neki Gazi-aga, 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. 1757. godine je bosanski valija Sopa Salan Ćamil-Ahmed-paša iz temelja 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. Ovaj opis u potpunosti odgovara sadašanjem stanju objekta, pa je vjerovatno da je ovaj dio objekta preživio požar koji je 1815. godine zahvatio Donju čaršiju, a sa njom i džamiju.
Nakon ovog požara iz 1815. godine, džamiju je temeljito obnovio 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. Pored obnove ove džamije, on je sagradio turbe nad mezarom bosanskog vezira Mustafe-paše Jenišeherlije u dvorištu Kukavičine medrese u Gornjoj čaršiji, te obnovio sahat-kulu kod Hadži Ali-begove džamije. Za održavanje ovih objekata ostavio je bogat, vezirski vakuf, a samoj džamiji je poklonio i ostavio na čuvanje visoko tursko odlikovanje koje je on primio za vojne zasluge.
O dešavanjima u vezi sa Šarenom džamijom od 1815. godine do danas se malo zna. Iz historijskih podataka zaključuje se da je tokom bombardiranja Travnika u II svjetskom ratu porušen zapadni ugao objekta i već 1945. godine je on obnovljen.
Enterijer Sulejmanije (šarene) džamije je posebno bogato dekorisan. Naročito se ističu lijepo slikane ornamentalne partije nad mihrabom i lučnim poljima nad prozorima. Na galeriji iznad prozora u kaligrafski izvedenom arapskom pismu ispisana su imena najbližih ashaba Muhammeda, s.a.v.s. Živopisno je ukrašena kasetirana tavanica i drveni stubovi koji nose galeriju i stropnu konstrukciju. Munara se nalazi na lijevoj umjesto na desnoj strani džamije kako je, inače, pravilo kod gradnje džamija. Pretpostavlja se da je munara starija od džamije i da potiče od prethodne Ćamilije.
U periodu prije 1992. godine Šarena džamija je restaurirana, bezistan stavljen u funkciju i rekonstruisan nekadašnji zanatsko-trgovinski centar oko nje.
Sadašnji imami džamije su: dr. hfz. Džemail-ef. Ibranović i Asim-ef. Muharemović.
U džamiji se klanjaju svi dnevni namazi i džuma-namaz. Mektepska nastava se izvodi četiri dana u sedmici. Na području džemata se nalaze i dvije tekije koje djeluju u okviru Islamske zajednice: nakšibendijsko-halidijska tekija u Lončarici džamiji i nakšibendijska tekija u Osojskoj džamiji.