Šarena (Časna, Atik, Gradska, Behram-begova) džamija izgrađena je 1888. godine na mjestu gdje je bila najstarija tuzlanska džamija izgrađena prije 1533. godine. Džamija,  medresa i mekteb izgorjeli su u požaru koji je zadesio Donju Tuzlu 1871. godine. Šarenu džamiju projektovao je Franc Mihanović (adaptacije su rađene po projektu Franca Kurila). To je rijedak i izuzetan primjer džamije tog vremena i stila, a njenom značaju doprinosi originalna slikana dekoracija koja je sačuvala izvornost iako je djelimično malterisana na fasadama.

Prahistorijsko naselje u Donjoj Tuzli prostiralo se na padini desne strane rječice Jale, čiju najvišu tačku upravo i predstavlja dominantno mjesto gdje se danas nalazi Stara ili Šarena džamija. Tokom osmanske uprave, ova džamija je središte najstarije mahale grada Tuzle i utvrde (palanke) koja još obuhvata Čaršiju i Solni trg, te glavne javne institucije.

Početkom 17. stoljeća veliki vakif Tuzle Behram-beg, obnovlja Časnu (Atik) džamiju i gradi u blizini medresu. Medresu prvi put u pisanim izvorima spominje 1674. godine pod nazivom Collegium impiorum Softarum.
Kako se naziv džamije mijenjao i mahala se nazivala Džamijska, potom Časna pa Atik.

Zgrada stare džamije bila je od drveta i ćerpića kao ispune i sa unutrašnjim drvenim kubetom. Na ovom lokalitetu kao dijelovi jedinstvene cjeline bili su džamija, medresa a postojao je i Atik mekteb koji je kao vakuf uspostavljen u 16. stoljeću. Džamija, medresa i mekteb izgorjeli su u požaru koji je zadesio Donju Tuzlu 10. septembra 1871. godine.

Prije 1888. godine po projektu arhitekte Franca Mihanovića izgrađena je današnja zgrada džamije u pseudomaurskom maniru. Pripada tipu jednoprostornih džamija sa kupolom. Zbog dvobojene fasade karakteristične za pseudomaurske građevine i bojenog enterijera u narodnoj tradiciji poznata je pod imenom Šarena. Spajanje tradicijske arhitekture i stranih utjecaja rezultirali su stvaranjem posebnog arhitektonskog izraza. Reljefna i slikana dekoracija, koja je jedna od glavnih odlika pseudomaurskog manira, na Šarenoj džamiji u Tuzli je jedna od najljepših u Bosni i Hercegovini. Dekoracija na ovom objektu je reljefna i slikana.
Objekat je u osnovi dimenzija 10.29 x 12.90m. Ukupne dimenzije sofa su 7.00 x 4.60m. Visina zidanog dijela objekta iznosi cca. 10.00m a visina sofa od terena do vrha krova cca. 8.30m. Ukupna visina objekta do vrha alema na kupoli iznosila je cca. 17.00m, a do vrha novog četverovodnog krova cca 11.60m. Munara je do vrha alema visoka cca. 23.00m.

Kako je ubrzo došlo do oštećenja drvene konstrukcije kupole, arhitekt Franc Kuril je 1895. godine izradio projekat adaptacije, prema kojem je izvorna drvena kupola zamijenjena četverovodnim krovom. Kao takva i uz više obnova postoji i danas. Od 2018. godine izvodi se detaljna obnova Šarene džamije.

U haremu Šarene džamije u Tuzli danas se nalazi šest nišana starijih od kraja 19. stoljeća, a najstariji datirani je iz 1836. godine.

Obnovljena Behrambegova medresa iz 1893. godine bila je zgrada uglovnica, sa tri kraka. Zgrada je bila prizemnica, pokrivena ravnim krovom. Dužina ulazne jugozapadne fasade bila je 13m, krak prema istoku 15.5m a prema sjeveroistoku 33m. Objekat je zauzimao površinu od cca. 530m2. Ubrzo je nadograđen sprat i zgrada prekrivena krovom.

Godine 1939. medresa je uz sjeverno krilo dograđena u prizemlju i na spratu, kada su njeni ukupni kapaciteti porasli na dvadeset prostorija za nastavu i internat za 120 učenika. Medresa je prestala sa radom 1949. godine. Poslije zatvaranja medrese u zgradi su bile smještena ekonomska, potom medicinska te upravna škola, Historijski arhiv i Muzej istočne Bosne.
Nekonstrolisana i neplanska eksploatacija soli na prostoru nekadašnje Donje Tuzle, koju je pratilo tonjenje i slijeganje zemljišta, dovela je do propadanja i rušenja niza objekata. Zgrada Medrese u toku 1973. i početkom 1974. godine počela je naglo propadati, što je dovelo do rušenja objekta u aprilu 1974. godine.
Inicijativom akademskog slikara Mevludina Ekmečića iz Tuzle sačuvan je ulazni portal u medresu, koji je nakon rušenja ostalog dijela zgrade restauriran krajem februara 1975. godine. Portal je kasnije više puta obnavljan.