Narodna tradicija veli da je to najstarija džamija u južnoj Hercegovini, koja je prema usmenom predanju podignuta od strane Kotezlije Muje, koji je pored džamije podigao i mekteb, te je i sam ukopan u mezaru koji se nalazi ispred pročelja džamije.
U Kotezima pored ove džamije tokom turske uprave izgrađeni su i spomenuti mekteb, dvije čatrnje, tri kule, više čardaka i stambenih objekata. Od svih ovih objekata malo je šta ostalo, većina je gotovo nestala, a ono malo ostataka još nekako stoji, zarasli i u veoma lošem stanju.
Jedino, koliko toliko sačuvani objekat je sama džamija, koja je izgrađena u centru mjesta i njena valjkasta, od kamena munara, i dan danas stoji prkoseći vremenu.
Osnova džamije je četverougao, vanjske veličine od 7,70 metara puta 10,10 metara, sa po dva prozora u zidu od mihraba i vrata, te po jedan mali pri vrhu druga dva zida.
Građena je od lomljenog kamena vezanog krečom, a zidovi su joj bili debeli 0,65 metara. Četverovodni, drveni krov je bio pokriven kamenim pločama. Uz samu džamiju stoji i cilindrična, posebno naočita munara, koja je, također, građena od lomljenog kamena, te koja ima krov koji je iznutra obložen crvenom opekom.
Pri vrhu munare nalaze se četiri mala prozora s kojih se nekada čuo ezan. Kameni mihrab smješten na jugoističnom zidu džamije ima poluobličasto udubljenu nišu širine 0,93 metara i visine oko 2,20 metara koja je pri vrhu zasvedena.
Okvir niše izlazi iz korpusa zida oko 15-20 cm i ima širinu 1,55 metara i visinu od oko 2,70 metara.
Džamija ima nekoliko mezara u svom haremu sa starim nišanima bez natpisa a sastavni dio kompleksa džamije su dvije čatrnje koje su sagrađene neposredno uz džamiju sa njene sjeveroistočne strane. Jugozapadno od objekta džamije nalaze se ostaci mektebske zgrade u kojoj se nalazio i stan za mualima.
Objekat spoljnih gabaritnih dimenzija oko 5 puta 10 metar, zidan je od tesanog kamena krečnjaka. Za vrijeme ustanka u Hercegovini (1875.-1878.), džamija je bila znatno oštećena i srušen joj je krov. Na fotografiji koja datira iz perioda prije 1939. godine vidljivo je da je objekat džamije bio popravljen i pokriven. Iz članka, u kojem je opisano putovanje reisu-l-uleme Fehima ef. Spahe kroz Hercegovinu i posjetu Kotezima, da se zaključiti da je objekat džamije bio u funkciji.
Džamija je ponovo stradala 1942. godine, kada je sa nje skinut krov, te srušena i mektebska zgrada u kojoj se nalazio i stan za mualima što je prouzrokovalo kasnije progresivno propadanje zidnih struktura, podova objekta, prozora i vrata i uopće enterijera ovih objekata. Džamija i mekteb su od tada van funkcije. Nema podataka da su bili popravljani i ne održavaju se.
