Xhamia Husa Medin Pasha i përket stilit të hershëm të arkitekturës osmane të Kostandinopojës. Mihrabi tetëkëndor me hark të cekët në anën jugore e dallon këtë ndërtesë nga ndërtesat e tjera të ruajtura të këtij lloji në Maqedoni. Kjo formë mihrabi, e njohur që nga shekulli i 14-të, u ndikua nga arkitektura e vonë bizantine dhe e hershme osmane.
Xhamia është një ndërtesë me një kupolë me bazë katrore, me përmasa të pastra prej 9.1 m, e mbuluar me një kupolë dhe një verandë të hapur të shtuar mbi katër shtylla, të mbuluar me tre kupola të vogla të ulëta.
Në cepin e brendshëm verior të xhamisë ndodhej një mahfil, i cili shërbente për lutjen e grave. E vetmja pjesë e ruajtur e mahfilit janë shkallët prej guri të ndërtuara brenda murit, të cilat të çonin në pjesën e galerisë, një nivel më të lartë se kati përdhes. Në cepin jugor të xhamisë ka gjurmë të minberit. Ndriçimi i brendshëm zgjidhet përmes tre rreshtave të dritareve. Hapjet e dritareve janë bërë nga blloqe guri të përpunuar dhe janë të harkuara.
Veranda e xhamisë ka një formë të thjeshtë dhe proporcionale, tipike për arkitekturën islame të shekullit të 16-të. Ajo mbështetet nga katër kurora kolonash mermeri. Dy të brendshmet janë prej mermeri të gjelbër dhe kanë kapitele dekorative, ndërsa të jashtmet janë prej mermeri të bardhë me kapitele dekorative në formën e “trekëndëshave turq”. Harkat që mbështesin kupolat janë bërë duke alternuar përdorimin e blloqeve të gurit të kuq dhe të bardhë, duke krijuar një efekt dekorativ mbresëlënës.
Ky sistem dekorimi zbatohet edhe mbi hyrjen kryesore, në anën veriore të ndërtesës, si dhe në dritaret e vendosura në anët e hyrjes, dhe është tipik për ndërtesat osmane nga gjysma e parë e shekullit të 16-të.
Minarja në anën perëndimore të xhamisë është ortogonale, e ndërtuar me gur ranor të gjelbër të sjellë nga zona e Shtipit. Minarja, sipas formës së saj, ka shumë të ngjarë të jetë e papërfunduar – pa sherefe dhe kulaf, dhe poroziteti natyror i gurit ranor të gjelbër është një nga arsyet e dëmtimit të saj. Shkallë guri janë ndërtuar në brendësi të minares.
Pranë xhamisë, në anën perëndimore, ndodhet një varr tetëkëndësh, i mbuluar me pllaka. Në të është varrosur Shejh Muhyudin Rumi (Baba). Varri është rinovuar disa herë, kështu që origjinaliteti i tij është dëmtuar dhe pamja e tij autentike nuk mund të përcaktohet.
