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.
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.
