Locirana je u centru i slovi kao najstarija, najveća i najljepša džamija u stolačkom kraju. Iz natpisa napisanog tušem i lijepim nashta’lik pismom na ploči iznad ulaznih vrata, razumije se da je sagrađena 925. (3. januara do 22. Decembra 1519.) godine. U svim izvorima u kojima se spominje ova džamija navodi se da je ona sagrađena za vrijeme i na ime sultana Selima I (Javuza koji je vladao od 1512. do 1520. godine). Natpis (tarih) je oštećen djelimično čitljiv i više puta opravljan. On je problematičan i, sigurno, nije nasto u vrijeme dovršenja izgradnje džamija. Prvobitni natpis, ako je uopće postojao, nastao je prilikom neke njene opravke. Ova džamija se ubraja među nekoliko najstarijih islamskh sakralnih spomenika u Bosni i Hercegovini i u tome je njen poseban značaj.
U pretursko doba nalazio se na sred stolačke džamije pravoslavni manastir i groblje oko njega. Priča se da je džamija sagrađena na temeljima manastira i da se ova mahala ranije zvala Carina. Tlocrt džamije upućuje na mišljenje da je ona, zaista, sagrađena na temeljima nekog starijeg kršćanskog hrama. Od izgradnje džamije mahala nastala oko nje zove se Careva mahala, Velika čaršija i Čaršija.
Priča se da je sultan Selim i poslao novac s naredbom (ferman) da se u Stocu sagradi džamija pod kupolom. Odbor za izgradnju džamije doveo je majstore s otoka Korčule, koji su bili poznati i dobri klesari, s njima sklopili ugovor za izgradnju džamije i odmah im polovinu pogođenog iznosa isplatili. Domalo iza toga oni su jedne noći bez traga nestali. Po jednog verziji ovog predanja oni su pobjegli u Crnu Goru, a po drugoj u Dubrovnik. Kada je o ovome obaviještena Porta, došla im je uz prekor druga naredba da s preostalim dijelom novca sagrade džamiju u Stocu, što je i učinjeno.
Džamija je sagrađena od tesanog kamena i pokrivena je četverostrešnim krovom. Osnovica joj je pravougaonik izdužen u smjeru istok-zapad i sa stranicama 16,55×9,25 metara (enterijer). Mihrab bez stalaktitnog dekora, i kameni minber, sagrađeni su u središnjem dijelu pročelnog zida. U uglu desno od ulaza nalazi se mahfil, koji se do 1930. godine protezao u širini cijele džamije. Lijevo od ulaza sagrađena je 1930. godine mala prostorija u kojoj za vrijeme ramazana stanuje mu’tekif. Uz desni zid joj je prigrađena kamena munara, prizmasta oblika, visoka 26 metara. Pred džamijom se nalaze prostrane sofe sa šadrvanom.
Ova je džamija u prošlosti više puta opravljana. Sve opravke džamije i mekteba uz nju, kao i plaćanje njihovih službenika, finansirala je država i neki stolački vakufi, jer ona, kao i ostale carske džamije u Bosni i Hercegovini, nije imala nikakva vakufa ni prihoda.
