Hamami i Gazi Mehmed Pashës gjendet në qendër të qytetit, pranë xhamisë së Kukli-Mehmed Beut dhe xhamisë së Emin Pashës. Është ndërtuar në vitet 1563-74, nga Gazi Mehmet Pasha, sanxhakbej i Shkodrës më 1573-4. Në portën kryesore është vendosur pllaka me mbishkrim e cila tregon datën e restaurimit të hamamit nga ana e vëllezërve Tahir dhe Mehmed Pashë Rrotulli (1833). Hamami gjendet në kuadër të ansamblit arkitektonik të themeluar nga Gazi Mehmet Pasha, ku gjenden Xhamia e Bajraklisë, shkolla e mesme (medreseja), shkolla fillore (mejtepi), biblioteka dhe mauzoleumi (tyrbja). Hamami është i llojit “çifte hamam”, i shfrytëzuar nga të dy gjinitë në të njëjtën kohë. Është ndërtuar me gurë të ndryshëm. Hamami i ka të gjitha hapësirat që i kanë edhe hamamet e këtij lloji, pra, përbëhet prej pjesës hyrëse (pjesa për pritje dhe për pije), pjesës së gardërobës, pjesës qendrore ku bëhej larja, djersitja, dëfrimi si dhe pjesës së kaldajës që gjendet në pjesën jugore të objektit. Hamami është ndërtuar nga gurë të ndryshëm në kombinim me tulla. Muret kanë një trashësi prej rreth 90 cm, të suvatuara nga ana e brendshme. Pullazi i objektit ka dy kupola të ndërtuara mbi tambure, në pjesën e ftohtë (pritja) dhe nëntë kupola të vogla mbi pjesën e ngrohtë të Hamamit. Pjesa e gardërobës dhe e kaldajës janë të mbuluara me qemer. Në pjesën e ftohtë mbulesa është me tjegulla, ndërsa pjesa tjetër me pllaka plumbi. Hamami deri në vitin 1964 ka qenë i rrethuar me lokale. Pas rrënimit të lokaleve fillojnë punët restauruese-konservuese. Edhe në vitet 70-të të shek. XX bëhen disa renovime, më pastaj lihet në mëshirë të kohës. Prej vitit 2000, pjesa e ftohtë e hamamit shfrytëzohet si galeri për organizimin e aktiviteteve të ndryshme kulturore, artistike dhe edukative.