Prema sakupljenim podacima u Travniku je od prve decenije XVI stoljeća, pa sve do 1878. godine, tj. do kraja osmanske vlasti, izgrađeno 16 džamija. Od navedenog broja četiri se ističu po svojoj starini i arhitektonskom bogatstvu: Jeni džamija sagrađena 1549. godine, Derviš pašina iz 1862. godine, Alibegova iz 1865. godine i Sulejmanija ili Šarena džamija izgrađena 1816. godine.

Sulejmanija ili Šarena džamija doživjela je nekoliko dogradnji i popravaka. Važi za najpoznatiju džamiju u Travniku, na Baščaršiji. Prvu je sagradio na identičnom mjestu Gazi aga krajem XVI stoljeća, ali kako je bila od drveta brzo je oronula pa ju je 1757. godine obnovio beglerbeg Ćamil Ahmed paša. Prilikom izgradnje Ćamil je uz nju izgradio i bezistan sa 27 trgovina, temeljito obnovio vodovod te uredio džamijski trg. Požar koji je zahvatio džamiju 1815. godine zahtijevao je njezinu novu obnovu, što je i učinio Sulejman paša Skopljak, po kome će džamija i dobiti novi naziv Sulejmanija.

Također, po njegovoj želji zidovi su išarani pa je džamija dobila i naziv “Šarena”. Naime džamija je iznutra i spolja obojena po okrečenim zidovima i po drvenariji i ukrašena raznim šarama. Taj posao su obavili domaći nakaši (moleri). Tridesetih godina XX stoljeća tadašnje Vakufsko povjerenstvo Kraljevine Jugoslavije je izdalo nalog da se šare u unutrašnjosti obnove premazivanjem po starim uzorima, a na vanjskim zidovima preboje arabeskama, čime je učinjeno više štete nego koristi. U periodu nakon gradnje Sulejmanijom su je nazivali muslimani, dok je termin “Šarena” korišten od nemuslimanskih stanovnika. Dimenzije džamije sa glavne – vanjske strane su 21,98 x 16 metara, dok je bezistan u unutrašnjosti širok 8,20 a dugačak 12,30 metara, sa hodnikom širine 2,68 metara. Prostor gdje se obavlja molitva ima površinu 14,10 x 15,15. Munara se nalazi na lijevoj strani džamijskog prostora i potiče još od vremena Gazi age. Džamija se ističe originalnim stilom kakvim su građene stare džamije u anadolskom Eskišehiru, a nema je slične ni u Istanbulu niti u drugim mjestima na Balkanu, izuzev Šuster džamije u Peći, ali koja je srušena od strane italijanske vojske u Drugom svjetskom ratu. Sa dvije strane su izgrađene kolonade na zdepastim stubovima, iza kojih je prolaz ispred niza trgovina. Sam bezistan ima dva reda trgovina, od kojih neke imaju magaze kao ardije, pomoćne prostorije i sl. Bezistan više ne služi za trgovinu već kao skladište za sir, voće i povrće. U periodu nakon izgradnje na jugoistočnoj strani džamije, bio je i red stolova na kojima su ekmeščije (pekari) prodavali hljeb. Preko puta džamije, kod jugoistočnog ugla, nekada se nalazila kafana “Merkez” ili “Central” u kojoj su se, po starom običaju, tokom zimskih večeri održavala predavanja iz historije i tumačenja Kajimijine “Kaside”. Simpatični starac koji je radio u njoj u narodu je zvan Krpo, dok mu je pravo ime bilo Muhamed. Obzirom da je bio siromašan i da nije mogao pokriti troškove kirije, radio je kao obućar ispod željezničkog mosta, u prolazu prema Varošu. Poslije svoje smrti tradiciju je preuzeo Šerif efendija Tahirović. Kafana “Merkez” je za Travničane bila nešto što je u osmanski vakat bila kafana u Gornjoj čaršiji, zvana “Pod lipom”, gdje su se sastajali travnički prvaci i janjičarske age.